Unit 2: Solution of Linear and Nonlinear Equations

I. Orientation: Equations in Robotics

Robotics uses mathematical equations to describe configuration, motion, forces, sensing, and control. Linear equations usually have the form (A\mathbf{x}=\mathbf{b}), while nonlinear equations involve functions such as (\sin\theta), products of unknowns, or powers higher than one. Numerical methods are essential when an exact symbolic solution is unavailable or computationally expensive.

• Linear model: (A\mathbf{x}=\mathbf{b}), where (A) is the coefficient matrix, (\mathbf{x}) is the vector of unknowns, and (\mathbf{b}) is the known-data vector.
• Square-system condition: For a square matrix (A), a unique solution exists when (\det(A)\neq0), equivalently when (A) is nonsingular.
• Eigenvalue convention: An eigenpair satisfies (A\mathbf{v}=\lambda\mathbf{v}), where (\lambda) is an eigenvalue and (\mathbf{v}\neq\mathbf{0}) is its eigenvector.
• Numerical stability: Small data or round-off errors can produce large solution errors when a matrix is ill-conditioned.
• Root-finding principle: Solving a scalar nonlinear equation means finding (x^) such that (f(x^)=0).
• Stopping convention: Iterations commonly stop when (|f(xk)|) or the step size (|x{k+1}-x_k|) is below a prescribed tolerance.

II. Factorization based on eigenvalues: Spectral Structure

A. Factorization based on eigenvalues

Factorization based on eigenvalues expresses a matrix through its eigenvalues and eigenvectors, revealing transformations that act independently along special directions.

• Eigenvalue equation:

A v_i = lambda_i v_i

Here, (A) is an (n\times n) matrix, (\lambda_i) is the (i)-th eigenvalue, and (\mathbf{v}_i) is its eigenvector.

• Diagonalization: If (A) has (n) linearly independent eigenvectors, then

A = V Lambda V^(-1)

where (V=[\mathbf{v}_1\ \cdots\ \mathbf{v}_n]) and (\Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)). Consequently, (A^k=V\Lambda^kV^{-1}), simplifying repeated matrix operations.

• Symmetric matrices: For real symmetric (A), eigenvectors can be chosen orthonormal, so (V^{-1}=V^T) and

A = Q Lambda Q^T

This orthogonal factorization is numerically more reliable.

• Connection with determinant: The determinant equals the product of eigenvalues, (\det(A)=\prod_i\lambda_i); therefore, a zero eigenvalue indicates singularity.
• Robotics use: Eigenvalues help analyze manipulability, stability, principal motion directions, and the conditioning of Jacobian or inertia matrices.

B. Applications and limitations

The spectral form is useful for analysis, but its existence and numerical usefulness depend on matrix properties.

• Positive definiteness: A symmetric matrix is positive definite when all eigenvalues are positive; this supports unique energy-minimizing solutions.
• Repeated eigenvalues: Repeated eigenvalues do not automatically prevent diagonalization, but there must still be enough independent eigenvectors.
• Defective matrices: If independent eigenvectors are insufficient, (A=V\Lambda V^{-1}) cannot be formed in the ordinary way.
• Conditioning: Eigenvalues near zero signal directions in which the matrix nearly loses information, making solutions sensitive to measurement noise.

III. Singular value decomposition: Robust Matrix Decomposition

A. Singular value decomposition

Singular value decomposition (SVD) factors every real matrix into orthogonal rotations or reflections and a nonnegative scaling matrix, making it valuable for rank-deficient and rectangular systems.

• Formal decomposition:

A = U Sigma V^T

For (A\in\mathbb{R}^{m\times n}), (U\in\mathbb{R}^{m\times m}) and (V\in\mathbb{R}^{n\times n}) are orthogonal, while (\Sigma) contains singular values (\sigma_1\geq\sigma_2\geq\cdots\geq0).

• Singular-vector equations: The columns satisfy (A\mathbf{v}_i=\sigma_i\mathbf{u}_i) and (A^T\mathbf{u}_i=\sigma_i\mathbf{v}_i), connecting SVD with eigenvalues of (A^TA): (\sigma_i=\sqrt{\lambda_i(A^TA)}).
• Rank: The number of nonzero singular values equals (\operatorname{rank}(A)). Zero singular values identify directions lost by the transformation.
• Least-squares solution: For an overdetermined system, SVD gives the minimum-error solution by resolving (A\mathbf{x}\approx\mathbf{b}) along orthogonal directions.
• Pseudoinverse:

A^+ = V Sigma^+ U^T
x = A^+ b

(\Sigma^+) replaces every nonzero (\sigma_i) by (1/\sigma_i) and transposes the rectangular layout.

• Robotics use: SVD detects singular robot configurations, computes inverse-kinematics least-squares steps, and measures manipulability through the Jacobian singular values.

B. Applications and limitations

SVD provides a controlled way to discard unreliable directions, but very small singular values require careful treatment.

• Truncated SVD: Singular values below a threshold can be set to zero, reducing noise amplification in sensor or Jacobian calculations.
• Condition number: For a full-rank matrix, (\kappa2(A)=\sigma{\max}/\sigma_{\min}); a large ratio indicates ill-conditioning.
• Computational cost: SVD is more expensive than solving a well-conditioned square system directly, although its stability often justifies the cost.

IV. Solution of nonlinear equations: Root-Finding Framework

A. Solution of nonlinear equations

The solution of nonlinear equations seeks a root of (f(x)=0), or, for several variables, a vector (\mathbf{x}) satisfying (\mathbf{F}(\mathbf{x})=\mathbf{0}).

• Nonlinearity examples: Equations such as (x^2-2=0), (\cos x-x=0), and robot equations containing (\sin\theta) are nonlinear because the unknown does not appear only to the first power in a linear combination.
• Root types: A simple root has (f(x^)=0) and (f'(x^)\neq0); a multiple root also has (f'(x^*)=0), often slowing iteration.
• Local versus global behavior: A method may converge rapidly near a root but fail when the initial estimate is poor or when the function has discontinuities.
• Multivariable extension: Newton's method replaces the derivative by the Jacobian (J(\mathbf{x})) and solves (J(\mathbf{x}_k)\Delta\mathbf{x}=-\mathbf{F}(\mathbf{x}_k)).
• Method selection: Bracketing methods prioritize guaranteed convergence, whereas open methods prioritize speed but require better initial information.

V. Bisection method: Guaranteed Bracketing

A. Bisection method

The bisection method repeatedly halves an interval whose endpoints have opposite function signs, guaranteeing convergence when the function is continuous.

• Existence condition: If (f) is continuous on ([a,b]) and (f(a)f(b)<0), the Intermediate Value Theorem guarantees at least one root in the interval.
• Iteration: Compute

c = (a + b)/2

If (f(a)f(c)<0), replace (b) by (c); otherwise replace (a) by (c). The midpoint (c) becomes the current approximation.

• Error bound: After (n) iterations, the interval width is ((b-a)/2^n), and the midpoint error is at most ((b-a)/2^{n+1}).
• Worked example: For (f(x)=x^2-2) on ([1,2]), (f(1)=-1) and (f(2)=2). The first midpoint is (1.5), with (f(1.5)=0.25), so the new bracket is ([1,1.5]).
• Strength: The sign-changing bracket remains available, making the method reliable even without derivatives.
• Limitation: Convergence is linear; the interval shrinks by only one-half per iteration, and an even-multiplicity root may not cause a sign change.

VI. Secant method: Derivative-Free Open Iteration

A. Secant method

The secant method approximates the derivative using two recent points, avoiding explicit differentiation while usually converging faster than bisection.

• Secant update:

x_(k+1) = x_k - f(x_k) * (x_k - x_(k-1)) / (f(x_k) - f(x_(k-1)))

The symbols (x_{k-1}) and (x_k) are the two latest estimates.

• Geometric meaning: The line through ((x{k-1},f(x{k-1}))) and ((x_k,f(x_k))) intersects the x-axis at the next estimate.
• Convergence: Near a simple root, the order is approximately (1.618), called superlinear convergence, compared with order 1 for bisection.
• Worked example: With (f(x)=x^2-2), (x_0=1), and (x_1=2), the next estimate is (x_2=2-2(1)/(2-(-1))=4/3), approaching (\sqrt2).
• Risk: If (f(xk)-f(x{k-1})) is zero or very small, the quotient is undefined or unstable; the next point can also leave the useful region.
• Comparison: Bisection maintains a guaranteed bracket; the secant method uses less structural protection in exchange for faster typical progress.

VII. Newton-Raphson method: Derivative-Based Quadratic Convergence

A. Newton-Raphson method

The Newton-Raphson method replaces the function locally by its tangent line and uses the tangent's x-intercept as the next root estimate.

• Iteration formula:

x_(k+1) = x_k - f(x_k)/f'(x_k)

Here, (f'(x_k)) is the derivative at the current estimate (x_k).

• Derivation: The tangent approximation is (f(x)\approx f(x_k)+f'(x_k)(x-x_k)). Setting this approximation to zero produces the update formula.
• Worked example: For (f(x)=x^2-2), (f'(x)=2x), and (x_0=1), (x_1=1-(1-2)/2=1.5); then (x_2=1.5-(2.25-2)/3\approx1.4167), rapidly approaching (1.4142).
• Convergence: For a sufficiently good initial estimate and a simple root, convergence is quadratic, so the number of correct digits often increases dramatically each iteration.
• Failure conditions: A zero derivative makes the update impossible; a very small derivative produces a large step, and a poor initial value can cause divergence or convergence to another root.
• Practical safeguards: Limit the step size, use damping (x_{k+1}=x_k-\alpha f(x_k)/f'(x_k)) with (0<\alpha\leq1), or combine Newton-Raphson with a bracketing method.
• Multivariable form: For (\mathbf{F}(\mathbf{x})=\mathbf{0}), solve

J(x_k) Delta_x_k = -F(x_k)
x_(k+1) = x_k + Delta_x_k

where (J) is the Jacobian and (\Delta\mathbf{x}_k) is the correction vector. In robotics, this form is central to iterative inverse kinematics.

B. Applications and limitations

The three methods make a practical hierarchy: reliability from bracketing, derivative-free acceleration from secants, and high local speed from Newton-Raphson.

• Bisection choice: Use it when continuity and a sign-changing interval are known but derivatives are unavailable or unreliable.
• Secant choice: Use it when function evaluations are available but derivative computation is costly or inconvenient.
• Newton-Raphson choice: Use it when an accurate derivative or Jacobian is available and a good initial estimate can be supplied.
• Stopping test: A robust implementation checks both (|f(x_k)|<\varepsilon_f) and (|xk-x{k-1}|<\varepsilon_x), along with a maximum iteration count.
• Robotics interpretation: Failure to converge may indicate an unsuitable initial pose, a kinematic singularity, incompatible task constraints, or sensor data inconsistent with the model.