Newton’s Method for Nonlinear Equations
CS/SE 4X03
Ned Nedialkov McMaster University March 5, 2021
Outline
Scalar case
Newton in 1D
Examples
Newton for systems of equations
Scalar case Newton in 1D Examples Newton for system Scalar case
• Given a scalar function f find a zero/root of f, i.e. an r such that f(r) = 0
• f may have no zeros, one, or many • Letrbearootoff andletxn ≈r
From
0 = f(r) = f(xn) + f′(xn)(r − xn) + O(|r − xn|2) 0 = f(r) ≈ f(xn) + f′(xn)(r − xn)
we find xn+1 by solving
f(xn) + f′(xn)(xn+1 − xn) = 0 (1)
Copyright © 2021 N. Nedialkov. All rights reserved. 3/13
Scalar case Newton in 1D Examples Newton for system Newton in 1D
• That is
xn+1 = xn − f(xn) (2) f′(xn)
• We start with an initial guess x0 and compute x1, x2, . . .
• How to choose x0, does it converge to a root, when to stop
iterating…?
Copyright © 2021 N. Nedialkov. All rights reserved. 4/13
Scalar case Newton in 1D Examples Newton for system Examples
Square root
• Given a > 0, compute √a
• Writex=√a,f(x)=x2−a • Apply (2):
xn+1 = xn − f(xn) = xn − x2n − a
2xn
f′(xn)
=xn−xn+ a 2 2xn a
=0.5 xn+xn
Copyright © 2021 N. Nedialkov. All rights reserved.
5/13
Scalar case Newton in 1D Examples Newton for system
• Leta=2andx0 =3
• We compute
i xi |xi− 2| 1 1.8333333333333333 4.19e-01 2 1.4621212121212122 4.79e-02 3 1.4149984298948031 7.85e-04 4 1.4142137800471977 2.18e-07 5 1.4142135623731118 1.67e-14 6 1.4142135623730949 2.22e-16
√
Copyright © 2021 N. Nedialkov. All rights reserved. 6/13
Scalar case Newton in 1D Examples Newton for system Examples cont.
Dividing without division operation
• How to obtain a/b without division?
• a/b=a∗(1/b)
• Find 1/b. Write f(x) = 1/x − b and apply (2)
xn+1 = xn − f(xn) = xn − 1/xn − b f ′ (xn ) −1/x2n
= xn + xn − bx2n = xn(2 − bxn)
Copyright © 2021 N. Nedialkov. All rights reserved. 7/13
Scalar case Newton in 1D Examples Newton for system Examples cont.
• Withb=3andx0 =0.3,wecompute i xi |xi − 1/3|
1 0.3300000000000000 3.33e-03
2 0.3333000000000000 3.33e-05
3 0.3333333300000000 3.33e-09
4 0.3333333333333333 5.55e-17
Copyright © 2021 N. Nedialkov. All rights reserved. 8/13
Scalar case Newton in 1D Examples Newton for system Newton for systems of equations
• Consider a system of n equations in n variables f1(x1,x2,…,xn) = 0
f2(x1,x2,…,xn) = 0 .
fn(x1,x2,…,xn) = 0
• Denote x = (x1,x2,…,xn)T and F = (f1,f2,…,fn)
• Find x∗ (if it exists) such that F(x∗) = 0
Copyright © 2021 N. Nedialkov. All rights reserved. 9/13
Scalar case Newton in 1D Examples Newton for system Newton for systems of equations cont.
• Assume x∗ is such that F(x∗) = 0 and x(k) ≈ x∗ • From
0=F(x∗)≈F(x(k))+F′(x(k))(x∗ −x(k)) find x(k+1) by solving (cf. (1))
F (x(k)) + F ′(x(k))(x(k+1) − x(k)) = 0 (3) • F ′(x(k)) is the Jacobian of F at x(k), an n × n matrix
Copyright © 2021 N. Nedialkov. All rights reserved. 10/13
Scalar case Newton in 1D Examples Newton for system Newton for systems of equations cont.
• Let s = x(k+1) − x(k)
• Solve (assuming F′(x(k)) nonsingular) linear system
and set
F ′(x(k))s = −F (x(k)) (4) x(k+1) = x(k) + s (5)
• (4,5) is basic Newton for systems of equations
Copyright © 2021 N. Nedialkov. All rights reserved. 11/13
Scalar case Newton in 1D Examples Newton for system Example
• Consider
• Jacobian is
• Let x0 = (5, 1)T
x21 + x2 − 25 0=F(x)= x21−x2−1
′ 2×1 2×2 F(x)= 2×1 −1
Copyright © 2021 N. Nedialkov. All rights reserved.
12/13
Scalar case Newton in 1D Examples Newton for system • Then
F (x(0)) = (1, 23)T
(0) 10 2
J(x )= 10 −1
• Solve J(x(0))s = −F(x(0)) • x(1) = x(0) + s and so on • We compute
i x1 x2 ∥F (x)∥
1 3.433333333333334 8.333333333333332 5.63e+01 2 2.632585333089088 5.289308176100628 9.93e+00 3 2.358810087435537 4.489032143454986 7.19e-01 4 2.329316858408983 4.424847176309882 5.06e-03 5 2.329040359270796 4.424428918660463 2.63e-07 6 2.329040339044829 4.424428900898053 7.11e-15
Copyright © 2021 N. Nedialkov. All rights reserved.
13/13