Unit 2: Solution of Linear and Nonlinear Equations - Subjective Questions

Definition: For a square matrix , a nonzero vector is an eigenvector if

where is the corresponding eigenvalue.

The eigenvalues are obtained from the characteristic equation

Eigenvalue-based factorization: If an matrix has linearly independent eigenvectors, form the matrix

and the diagonal matrix

Then

This is called eigenvalue decomposition or diagonalization. It simplifies matrix powers, systems of differential equations, stability analysis, and transformations used in robotics.

A square matrix of order is diagonalizable if it possesses linearly independent eigenvectors. Equivalently, there must be an invertible matrix and a diagonal matrix such that

Sufficient conditions:

• has distinct eigenvalues.
• For every eigenvalue, its geometric multiplicity equals its algebraic multiplicity.
• Every real symmetric matrix is diagonalizable by an orthogonal matrix.

Consider

Its eigenvalues are and , with eigenvectors

Thus,

and therefore . A matrix with fewer than linearly independent eigenvectors cannot be diagonalized.

Let be a real symmetric matrix, so that . According to the spectral theorem:

• All eigenvalues of are real.
• Eigenvectors corresponding to distinct eigenvalues are orthogonal.
• A complete orthonormal set of eigenvectors exists.

Let the normalized eigenvectors be , and define

Because the columns are orthonormal,

so . If

then

Multiplying by gives

Equivalently,

Significance:

• It expresses as a sum of rank-one matrices.
• It simplifies the computation of matrix powers and functions.
• It is useful in covariance analysis, principal component analysis, robot dynamics, and stability analysis.
• The orthogonal matrix provides numerically stable coordinate transformations.

The singular value decomposition, or SVD, of a real matrix is

where:

• is an orthogonal matrix whose columns are the left singular vectors.
• is an orthogonal matrix whose columns are the right singular vectors.
• is a rectangular diagonal matrix containing nonnegative singular values.

The singular values are conventionally ordered as

where . They satisfy

The right singular vectors are eigenvectors of , while the left singular vectors are eigenvectors of . Since and are orthogonal,

SVD exists for every real matrix, including rectangular and rank-deficient matrices.

For a matrix , the SVD is

It can be computed through the following steps:

1. Form the symmetric matrix .
2. Find its eigenvalues and normalized eigenvectors:

3. Arrange the eigenvectors as columns of .
4. Compute the singular values using

and arrange them in descending order along the diagonal of .

5. For each nonzero singular value, calculate the corresponding left singular vector:

6. If necessary, complete with additional orthonormal vectors.

Alternatively, the columns of can be obtained as eigenvectors of . The relationships

and

connect the left and right singular vectors.

Eigenvalue decomposition:

• Applies directly only to square matrices.
• Has the form .
• Requires enough linearly independent eigenvectors for diagonalization.
• Eigenvalues may be positive, negative, zero, or complex.
• The matrix is not necessarily orthogonal.

Singular value decomposition:

• Applies to every square or rectangular matrix.
• Has the form .
• Always exists for real and complex matrices.
• Singular values are always real and nonnegative.
• The matrices and are orthogonal for real matrices.

Relationship: The singular values of are the square roots of the eigenvalues of :

Eigenvalue decomposition describes invariant directions of a square transformation, whereas SVD describes the rotation, scaling, and further rotation associated with a general linear transformation.

Let the SVD of be

The Moore-Penrose pseudoinverse of is

where is obtained by:

• Taking the reciprocal of every nonzero singular value.
• Transposing the resulting rectangular diagonal matrix.
• Leaving zero singular values unchanged.

If

then

For the system , the SVD-based solution is

If the system is inconsistent, this gives a least-squares solution minimizing . If infinitely many solutions exist, it gives the solution with minimum Euclidean norm. In robotics, this is useful for inverse kinematics when the Jacobian is rectangular or rank-deficient.

Let the singular values of be

Rank: The rank of equals the number of nonzero singular values:

In numerical computations, singular values below a selected tolerance are treated as zero.

Condition number: For a full-rank matrix, the -norm condition number is

A condition number close to indicates a well-conditioned system. A very large condition number indicates that small errors in the input may produce large errors in the solution.

Numerical stability:

• A very small indicates near singularity.
• Zero singular values indicate exact rank deficiency.
• Small singular values amplify measurement and rounding errors when a pseudoinverse is computed.

In robotics, this analysis helps detect Jacobian singularities and identify configurations where commanded end-effector motion may require excessively large joint velocities.

A nonlinear equation is an equation of the form

where is not a linear function of . Examples include

Unlike a linear equation, a nonlinear equation may have no real root, one root, multiple roots, or infinitely many roots.

Main numerical difficulties:

• A closed-form solution may not exist.
• Different initial guesses may lead to different roots.
• Some methods may converge slowly or fail to converge.
• Discontinuities and singularities can mislead an iterative method.
• Repeated roots may reduce the convergence rate.
• Derivatives may be unavailable, expensive, or zero near a root.
• A stopping criterion must balance accuracy and computational cost.

Common numerical approaches include bracketing methods, such as bisection, and open methods, such as secant and Newton-Raphson.

An iterative root-finding method generates approximations . The computation should stop when a suitable accuracy criterion is satisfied.

Common stopping criteria:

• Absolute change in successive approximations:

• Relative change:

• Small residual:

• Maximum number of iterations is reached.

For the bisection method, the interval width can be used:

Error measures: If the exact root is known, the absolute and relative errors are

and

In practice, the exact root is usually unknown, so a combination of step-size, residual, and iteration-limit criteria should be used.

The bisection method is a bracketing method used to solve

Choose an interval such that is continuous and

By the Intermediate Value Theorem, at least one root lies in .

At each iteration, calculate the midpoint

Then:

• If , is the root.
• If , replace by .
• Otherwise, replace by .

The process is repeated until the interval or residual is sufficiently small.

Convergence conditions:

• must be continuous on .
• The endpoints must satisfy .
• The selected interval should not contain a discontinuity.

The method has guaranteed linear convergence when these conditions hold, although it is generally slower than the secant and Newton-Raphson methods.

Let the initial interval containing a root be . Its length is

Each bisection divides the interval length by . After iterations, the interval length is

If is the midpoint of the interval and is the actual root, the maximum midpoint error is half the current interval length:

A commonly used conservative bound is

To ensure that the interval length is at most , require

Taking logarithms gives

Therefore, the required integer number of iterations is

This predictable error reduction is an important advantage of the bisection method.

Given

At the endpoints,

Since , a root lies in .

Iteration 1:

Since and , the new interval is

Iteration 2:

Since and , the new interval is

Thus, after two iterations, the root is bracketed in , and the latest midpoint approximation is .

Suppose and are two approximations to a root of . The secant line through the points

and

has slope

Using the point-slope equation through ,

The next approximation is the -intercept of this line, so set :

Solving for gives

Geometric interpretation: The secant through two points on the graph of intersects the -axis at the next approximation. The method approximates the derivative using a finite difference and therefore does not require explicit derivative evaluation.

The secant method uses two initial approximations and the iteration

For a sufficiently smooth function and initial values close to a simple root, its order of convergence is approximately

Thus, it is superlinearly convergent: generally faster than bisection but slower than the quadratic convergence of Newton-Raphson.

Advantages:

• It does not require .
• It generally converges faster than bisection.
• Only one new function evaluation is normally needed per iteration.

Limitations:

• Convergence is not guaranteed.
• Poor initial guesses may cause divergence or convergence to an unintended root.
• The method fails when because the denominator becomes zero.
• It does not necessarily retain a bracket around the root.
• It can behave poorly near repeated roots or discontinuities.

The secant iteration is

For ,

First improved approximation:

Now,

Second improved approximation:

Since

we obtain

Thus, the first two improved approximations are and , approaching .

Let be an approximation to a root of

The tangent line to the curve at is

The next approximation is taken as the point where this tangent intersects the -axis. Setting gives

Therefore,

The same formula follows from the first-order Taylor expansion

Setting the approximation equal to zero gives

and hence .

For a sufficiently smooth function, a simple root, and an initial guess close enough to the root, Newton-Raphson has quadratic convergence.

To compute , solve

Since , the Newton-Raphson formula is

or

Starting with :

Iteration 1:

Iteration 2:

Iteration 3:

Therefore,

after three Newton-Raphson iterations. The rapid increase in accuracy illustrates quadratic convergence.

Newton-Raphson uses

For quadratic convergence to a simple root , the function should be sufficiently smooth near , , and the initial guess should be sufficiently close to the root.

Common failure cases:

• If , the next iterate is undefined.
• If is very small, an excessively large step may occur.
• A poor initial guess may cause divergence or convergence to another root.
• The iterates may oscillate between points without approaching a root.
• The method may enter a cycle.
• A discontinuity between iterates can produce misleading results.
• At a repeated root, standard Newton-Raphson loses quadratic convergence and usually becomes linearly convergent.

For a root of multiplicity , convergence can be improved using

Practical implementations also impose residual, step-size, derivative, and iteration-limit checks.

Bisection method:

• Requires two endpoints and satisfying .
• Requires continuity on the interval.
• Has guaranteed linear convergence.
• Does not require derivatives.
• Is highly reliable but comparatively slow.

Secant method:

• Requires two initial approximations.
• Does not require a sign-changing bracket.
• Does not require derivatives.
• Has superlinear convergence of order approximately near a simple root.
• Is faster than bisection but less reliable.

Newton-Raphson method:

• Usually requires one initial approximation.
• Requires evaluation of both and .
• Has quadratic convergence near a simple root under suitable conditions.
• Is often the fastest of the three methods.
• Can fail when the derivative is zero or when the initial guess is poor.

Thus, bisection is preferred when reliability is essential, Newton-Raphson when a derivative and good initial guess are available, and secant when derivative evaluation is difficult.