1
$\begingroup$

Is it possible to solve a linear matrix system $A x = b$ using the Newton-Raphson method? If yes, how can this be done? More special, how is the derivative build?

$\endgroup$
4
  • 1
    $\begingroup$ Newton’s method for this would very likely involve solving the system as a sub-step, so likely you wouldn’t see this help much. On the other hand, you could use some form of gradient descent effectively (indeed, one can view conjugate gradients in this way, and that works quite well in many situations). $\endgroup$
    – cdipaolo
    Nov 5, 2019 at 21:40
  • 1
    $\begingroup$ @cdipaolo Plain gradient descent for linear systems is known as "Richardson iteration". $\endgroup$ Nov 15, 2019 at 13:22
  • $\begingroup$ @FedericoPoloni Ah I hadn't seen that before. Thanks for the comment! $\endgroup$
    – cdipaolo
    Nov 15, 2019 at 21:29
  • $\begingroup$ No problem! For a quick comment: as you can probably expect, plain gradient descent is not too effective in practice. As far as I know, it is only used as a smoother in multigrid, and as a last resource for some ridiculously huge linear systems such as quantum chemistry where you only have $A$ in black-box form and you lack the space to run Arnoldi. $\endgroup$ Nov 16, 2019 at 9:33

1 Answer 1

9
$\begingroup$

Yes you can do this, and it will converge in one iteration regardless of the starting value.

This is because each step of Newton's method involves solving a linear system with the Jacobian of the nonlinear function. In this case the Jacobian just equals $A$.

In other words: this is a little circular because it requires you to solve the system $Ax=b$ in the first place, which doesn't help.

$\endgroup$
2
  • 2
    $\begingroup$ And the linear system you have to solve in each step of the Newton method is $Ax=b$ :-) $\endgroup$ Nov 5, 2019 at 22:20
  • $\begingroup$ yes, updated to make it clear it is not a good idea. $\endgroup$ Nov 5, 2019 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.