Solution of a linear system

 

Solution of a linear system[edit]

The steepest descent algorithm applied to the Wiener filter^[11]

Gradient descent can be used to solve a system of linear equations

${\displaystyle �\mathbf{�}-\mathbf{�}=0}$

reformulated as a quadratic minimization problem. If the system matrix ${\displaystyle �}$ is real symmetric and positive-definite, an objective function is defined as the quadratic function, with minimization of

${\displaystyle �(\mathbf{�})={\mathbf{�}}^{�}�\mathbf{�}-2{\mathbf{�}}^{�}\mathbf{�},}$

so that

${\displaystyle \mathrm{\nabla }�(\mathbf{�})=2(�\mathbf{�}-\mathbf{�}).}$

For a general real matrix ${\displaystyle �}$, linear least squares define

${\displaystyle �(\mathbf{�})={\Vert �\mathbf{�}-\mathbf{�}\Vert }^2.}$

In traditional linear least squares for real ${\displaystyle �}$ and ${\displaystyle \mathbf{�}}$ the Euclidean norm is used, in which case

${\displaystyle \mathrm{\nabla }�(\mathbf{�})=2{�}^{�}(�\mathbf{�}-\mathbf{�}).}$

The line search minimization, finding the locally optimal step size ${\displaystyle �}$ on every iteration, can be performed analytically for quadratic functions, and explicit formulas for the locally optimal ${\displaystyle �}$ are known.^[5][12]

For example, for real symmetric and positive-definite matrix ${\displaystyle �}$, a simple algorithm can be as follows,^[5]

To avoid multiplying by ${\displaystyle �}$ twice per iteration, we note that ${\displaystyle \mathbf{�}:=\mathbf{�}+�\mathbf{�}}$ implies ${\displaystyle \mathbf{�}:=\mathbf{�}-�\mathbf{�}\mathbf{�}}$, which gives the traditional algorithm,^[13]

The method is rarely used for solving linear equations, with the conjugate gradient method being one of the most popular alternatives. The number of gradient descent iterations is commonly proportional to the spectral condition number ${\displaystyle �(�)}$ of the system matrix ${\displaystyle �}$ (the ratio of the maximum to minimum eigenvalues of ${\displaystyle {�}^{�}�}$), while the convergence of conjugate gradient method is typically determined by a square root of the condition number, i.e., is much faster. Both methods can benefit from preconditioning, where gradient descent may require less assumptions on the preconditioner.^[13]

Solution of a non-linear system[edit]

Gradient descent can also be used to solve a system of nonlinear equations. Below is an example that shows how to use the gradient descent to solve for three unknown variables, x₁, x₂, and x₃. This example shows one iteration of the gradient descent.

Consider the nonlinear system of equations

${\displaystyle \{\begin{array}{l}3{�}_1-\cos ({�}_2{�}_3)-\frac{3}{2}=0\\ 4{�}_1^2-625{�}_2^2+2{�}_2-1=0\\ \exp (-{�}_1{�}_2)+20{�}_3+\frac{10�-3}{3}=0\end{array}}$

Let us introduce the associated function

${\displaystyle �(\mathbf{�})=\left[\begin{array}{c}3{�}_1-\cos ({�}_2{�}_3)-\frac{3}{2}\\ 4{�}_1^2-625{�}_2^2+2{�}_2-1\\ \exp (-{�}_1{�}_2)+20{�}_3+\frac{10�-3}{3}\end{array}\right],}$

where

${\displaystyle \mathbf{�}=\left[\begin{array}{c}{�}_1\\ {�}_2\\ {�}_3\end{array}\right].}$

One might now define the objective function

which we will attempt to minimize. As an initial guess, let us use

${\displaystyle {\mathbf{�}}^{(0)}=\mathbf{0}=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right].}$

We know that

${\displaystyle {\mathbf{�}}^{(1)}=\mathbf{0}-{�}_0\mathrm{\nabla }�(\mathbf{0})=\mathbf{0}-{�}_0{�}_{�}(\mathbf{0}{)}^{\mathrm{T}}�(\mathbf{0}),}$

where the Jacobian matrix ${\displaystyle {�}_{�}}$ is given by

We calculate:

Thus

${\displaystyle {\mathbf{�}}^{(1)}=\mathbf{0}-{�}_0\left[\begin{array}{c}-7.5\\ -2\\ 209.44\end{array}\right],}$

and

${\displaystyle �(\mathbf{0})=0.5\left((-2.5{)}^2+(-1{)}^2+(10.472{)}^2\right)=\mathrm{58.456.}}$

An animation showing the first 83 iterations of gradient descent applied to this example. Surfaces are isosurfaces of ${\displaystyle �({\mathbf{�}}^{(�)})}$ at current guess ${\displaystyle {\mathbf{�}}^{(�)}}$, and arrows show the direction of descent. Due to a small and constant step size, the convergence is slow.

Now, a suitable ${\displaystyle {�}_0}$ must be found such that

${\displaystyle �\left({\mathbf{�}}^{(1)}\right)\le �\left({\mathbf{�}}^{(0)}\right)=�(\mathbf{0}).}$

This can be done with any of a variety of line search algorithms. One might also simply guess ${\displaystyle {�}_0=0.001,}$ which gives

${\displaystyle {\mathbf{�}}^{(1)}=\left[\begin{array}{c}0.0075\\ 0.002\\ -0.20944\end{array}\right].}$

Evaluating the objective function at this value, yields

${\displaystyle �\left({\mathbf{�}}^{(1)}\right)=0.5\left((-2.48{)}^2+(-1.00{)}^2+(6.28{)}^2\right)=\mathrm{23.306.}}$

The decrease from ${\displaystyle �(\mathbf{0})=58.456}$ to the next step's value of

${\displaystyle �\left({\mathbf{�}}^{(1)}\right)=23.306}$

is a sizable decrease in the objective function. Further steps would reduce its value further until an approximate solution to the system was found.