Department of Mathematics

Dr. Mohammed Salman

Eng. Shady Nagy

Miss Naglaa Ragab

Winter 2021

Mathematics

for IET Students (MATH-502)

Worksheet Nr. (3) solution

Newton’s Method
𝟏𝟏 𝟏
1. Apply Netwon’s Method to 𝒇(𝒙) = 𝟒𝒙𝟒 − 𝟔𝒙𝟐 − with starting guess 𝒙𝟎 = 𝟐.
𝟒

Solution

11
4𝑥𝑖4 − 6𝑥𝑖2 − 4
𝑥𝑖+1 = 𝑥𝑖 −
16𝑥𝑖3 − 12𝑥𝑖

This functions has roots, since its continuous, negative at 𝑥 = 0 goes to positive infinity for large positive
1
and negative values. However, no roots will be found for the starting guess 𝑥𝑜 = 2. Newton’s method
1 1
alternates on this problem between two roots 2 , − 2 and fails to find a root.

Newton’s method can fail in other ways, if 𝑓 ′ (𝑥𝑖 ) = 0 at any iteration, method cant be continued.

Failure of Newton’s Method . The iteration alternates between 1/2 and −1/2, and does not converge to a root.
2. Apply two steps of Newton’s Method with initial guess 𝒙𝟎 = 𝟎:
a) 𝒙𝟑 + 𝒙 − 𝟐 = 𝟎

b) 𝒙𝟒 − 𝒙𝟐 + 𝒙 − 𝟏 = 𝟎

c) 𝒙𝟐 − 𝒙 − 𝟏 = 𝟎

Solution

a)

𝑓(𝑥𝑖 )
𝑥𝑖+1 = 𝑥𝑖 −
𝑓′(𝑥𝑖 )

𝑥03 +𝑥0 −2 𝑥13 +𝑥1 −2

𝑓 ′ (𝑥) = 3𝑥 2 + 1 , 𝑥1 = 0 − = 2 , 𝑥2 = 2 − = 1.38415.
3𝑥02 3𝑥12

b)

𝑓(𝑥𝑖 )
𝑥𝑖+1 = 𝑥𝑖 −
𝑓′(𝑥𝑖 )

𝑥𝑖4 − 𝑥𝑖2 + 𝑥𝑖 − 1
𝑓 ′ (𝑥) = 4𝑥 3 − 2𝑥 + 1 , 𝑥𝑖+1 = 𝑥𝑖 −
4𝑥𝑖3 − 2𝑥𝑖 + 1

𝑥1 = 1, 𝑥2 = 1

c) 𝑓 ′ (𝑥) = 2𝑥 − 1,

𝑓(𝑥𝑖 )
𝑥𝑖+1 = 𝑥𝑖 −
𝑓′(𝑥𝑖 )

(−1)2 − (−1) − 1 2
𝑥1 = −1, 𝑥2 = (−1) − =−
2. (−1) − 1 3

Defintion

Let 𝒆𝒊 denotes the error, 𝒆𝒊 = |𝒓 − 𝒙𝒊 | at step 𝒊 of an iterative method. If

𝒆𝒊+𝟏
𝐥𝐢𝐦 =𝑺<𝟏
𝒊→∞ 𝒆𝒊

The method is said to obey linear convergence with rate S.

 𝟏
3. Consider the equation 𝟖𝒙𝟒 − 𝟏𝟐𝒙𝟑 + 𝟔𝒙𝟐 − 𝒙 = 𝟎 for each of the two solutions 𝒙 = 𝟎 and 𝒙 = 𝟐,
decide which will converge faster (say to eight place accuracy), the Bisection Method or Newton’s
Method, without running calculation.

Solution
1
We will check first if 𝑟 = 2 is a repeated root or 𝑥 = 0 isn’t repteated

8𝑥 4 − 12𝑥 3 + 6𝑥 2 − 𝑥 = 0

1 1 1
𝑥 (𝑥 − ) (𝑥 − ) (𝑥 − ) = 0
2 2 2

If 𝑓′(𝑟) ≠ 0, convergence of Newton is quadratic so it is faster than linear, and multiple root when 𝑓 ′ (𝑟) =
0 and it is slower till we use midified Newton method.

𝑎𝑡 𝑥 = 0 𝑓 ′ (𝑥) = 32𝑥 3 − 36𝑥 2 + 12𝑥 − 1, 𝑓 ′ (0) = −1

Convergence at 𝑓 ′ (0) ≠ 0, so it is quadratic convergence at this root. So Newton emthod is faster than
Bisection in finding this root.
1
𝑎𝑡 𝑥 = 2

1 1 1
𝑓 ′ ( ) = 0, 𝑓 ′′ ( ) = 0, 𝑓 ′′ ( ) ≠ 0 = 24
2 2 2

So the degree of differentiation 𝑚 = 3

𝑒𝑖+1 𝑚 − 1 2
= =
𝑒𝑖 𝑚 3
1
Newton’s method in this case is slower than Bisection Method at 𝑥 = 2
4. Sketch a function f and initial guess for which Newton’s Method diverges.

Solution

Let us consider the function, 𝑓(𝑥) = 𝑥 2 + 7𝑥 + 12, 𝑓 ′ (𝑥) = 2𝑥 + 7. Let us to find of 𝑥 which 𝑓 ′ (𝑥) = 0

7
2𝑥 + 7 = 0, 𝑥 = −
2
7
If we take initial guess as 𝑥0 = − 2, Newton’s method diverges as shown in the graph.

Defintion

If (𝒎 + 𝟏) times continuously differentiable 𝒇 𝒐𝒏 [𝒂, 𝒃] has multiplicity 𝒎 at root 𝒓, then Newton’s

Method is locally converegent to 𝒓

𝒆𝒊+𝟏 𝒎−𝟏
𝐥𝐢𝐦 = 𝑺 < 𝟏,𝑺 =
𝒊→∞ 𝒆𝒊 𝒎

5. Let 𝒇(𝒙) = 𝒙𝟒 − 𝟕𝒙𝟑 + 𝟏𝟖𝒙𝟐 − 𝟐𝟎𝒙 + 𝟖. Does Newton’s Method converge quadratically to the root
𝒆𝒊+𝟏
r=2? Find 𝐥𝐢𝐦 where 𝒆𝒊 denotes the error at step 𝒊.
𝒊→∞ 𝒆𝒊

Solution

Let’s find the derivatives of the function

𝑓(𝑥) = 𝑥 4 − 7𝑥 3 + 18𝑥 2 − 20𝑥 + 8

= (𝑥 − 2)3 (𝑥 − 1)
 Substitute with the 𝑥 = 2

𝑓 ′ (𝑥) = 4𝑥 3 − 21𝑥 2 + 36𝑥 − 20, 𝑓 ′ (2) = 0

So 𝑓(𝑥) doesn’t converge quadratically to the root 𝑟 = 2.

𝑓 ′′ (𝑥) = 12𝑥 2 − 42𝑥 + 36, 𝑓 ′′ (2) = 0

𝑓 ′′′ (𝑥) = 24𝑥 − 42 ≠ 0

Therefore, multpilicity of the root equals 3

𝑒𝑖+1 2 𝑚−1
lim= ,𝑆 =
𝑖→∞ 𝑒𝑖 3 𝑚

6. The function 𝒇(𝒙) = 𝒙𝟑 − 𝟒𝒙 has a root 𝒓 = 𝟐. If the error 𝒙𝒊 − 𝒓 after four steps of Newton’s Method
is 𝒆𝟒 = 𝟏𝟎−𝟔 , estimate 𝒆𝟓

Solution

Let’s find the first and second derivatives

𝑓 ′ (𝑥) = 3𝑥 2 − 4, 𝑓 ′′ (𝑥) = 6𝑥

Let 𝑓 be twice continuously differentiable and 𝑓(𝑟) = 0. If 𝑓′(𝑟) ≠ 0, then Newton’s method is locally
convergent to 𝑟 and convergence is quadratic.

𝑒𝑖+1 𝑓′′(𝑟)
lim = 𝑀, 𝑀 = | |
𝑖→∞ 𝑒 2 2𝑓′(𝑟)
𝑖

𝑓 ′′ (2) = 6 ∗ 2 = 12

𝑓 ′ (2) = 16

Then computes the value of 𝑀

3
𝑀=
4

𝑒𝑖+1 ≈ 0.75 ∗ 𝑒𝑖2 ≈ 0.75(10−6 )2 ≈ 0.75 ∗ 10−12

7. Find the multiplicity of the root 𝒓 = 𝟎 of 𝒇(𝒙) = 𝐬𝐢𝐧 𝒙 + 𝒙𝟐 𝐜𝐨𝐬 𝒙 − 𝒙𝟐 − 𝒙 and find the solution with
𝟏𝟎−𝟓 accuracy.

Solution

It is easy to check that

 𝑓 ′ (𝑥) = cos 𝑥 + 2𝑥 cos 𝑥 − 𝑥 2 sin 𝑥 − 2𝑥 − 1

𝑓 ′′ (𝑥) = − sin 𝑥 + 2 cos 𝑥 − 4𝑥𝑠𝑖𝑛 𝑥 − 𝑥 2 cos 𝑥 − 2

𝑓 ′′′ (𝑥) = − cos 𝑥 − 6 sin 𝑥 − 6𝑥 cos 𝑥 + 𝑥 2 sin 𝑥

𝑓 ′ (0) = 0, 𝑓 ′′ (0) = 0, 𝑓 ′′′ (0) = −1

2𝑒𝑖
meaning that the multiplicity is m = 3. Newton should converge linearly with 𝑒(𝑖+1) ≈ . Using starting
3
guess 𝑥0 = 1, we have 𝑒0 = 1. Near convergence, the error will decrease by 2/3 on each step.

If the multiplicity of a root is known in advance, convergence of Newton’s Method can be improved with a
small modification by using modified Newton’s Method
𝑓(𝑥𝑖 )
𝑥𝑖+1 = 𝑥𝑖 − 𝑚
𝑓′(𝑥𝑖 )

we can apply Modified Newton’s Method to achieve quadratic convergence. After five steps, convergence
to the 𝑟𝑜𝑜𝑡 𝑟 = 0 has taken place to about eight digits of accuracy:
we can apply Modified Newton’s Method to achieve quadratic convergence. After five steps, convergence
to the root r = 0 has taken place to about eight digits of accuracy.
Secant Method
8. Apply two steps of the Secant Method to the following equations with initial guesses 𝒙𝟎 = 𝟏, 𝒙𝟏 = 𝟐

a) 𝒙𝟑 = 𝟐𝒙 + 𝟏
b) 𝒆𝒙 + 𝒙 = 𝟕
c) 𝒆𝒙 + 𝐬𝐢𝐧 𝒙 = 𝟒

Solution

a)

Initial guess, 𝑥0 = 1, 𝑥1 = 2

𝑓(𝑥𝑖 )(𝑥𝑖 − 𝑥𝑖−1 )

𝑥𝑖+1 = 𝑥𝑖 −
𝑓(𝑥𝑖 ) − 𝑓(𝑥𝑖−1 )

Iteration formula of Secant method

(𝑥𝑖3 − 2𝑥𝑖 − 2)(𝑥𝑖 − 𝑥𝑖−1 )

𝑥𝑖+1 = 𝑥𝑖 −
(𝑥𝑖3 − 2𝑥𝑖 − 2) − (𝑥𝑖−1
3
− 2𝑥𝑖−1 − 2)

8
𝑥2 = , 𝑥3 = 1.742268041
5
b)

Initial guess, 𝑥0 = 1, 𝑥1 = 2

𝑓(𝑥𝑖 )(𝑥𝑖 − 𝑥𝑖−1 )

𝑥𝑖+1 = 𝑥𝑖 −
𝑓(𝑥𝑖 ) − 𝑓(𝑥𝑖−1 )
Iteration formula of Secant method

𝑒𝑥 + 𝑥 − 7 = 0

(𝑒 𝑥𝑖 − 𝑥𝑖 − 7)(𝑥𝑖 − 𝑥𝑖−1 )
𝑥𝑖+1 = 𝑥𝑖 −
(𝑒 𝑥𝑖 − 𝑥𝑖 − 7) − (𝑒 𝑥𝑖−1 + 𝑥𝑖−1 − 7 )

𝑥2 = 1.57807248, 𝑥3 = 1.660160100

c)

(𝑒 𝑥𝑖 + sin(𝑥𝑖 ) − 4)(𝑥𝑖 − 𝑥𝑖−1 )

𝑥𝑖+1 = 𝑥𝑖 −
𝑒 𝑥𝑖 + sin(𝑥𝑖 ) − 𝑒 𝑥𝑖−1 − sin(𝑥𝑖−1 )

𝑥2 = 1.092906580, 𝑥3 = 1.11935668
𝟏
9. Consider the following four methods for calculating 𝟐𝟒 , the fourth root of 2. Rank them by evaluating
the steps of the method and comapring speed of convergence, from fastest to slowest. Be sure to give
reasons for your ranking

a) Bisection Method 𝒇(𝒙) = 𝒙𝟒 − 𝟐

b) Secant Method applied 𝒇(𝒙) = 𝒙𝟒 − 𝟐
𝒙 𝟏
c) Fixed Point Iteration applied to 𝒈(𝒙) = 𝟐 + 𝒙𝟑
d) Are there any methods that will converge faster than all above suggestions?

Solution
1
a) Biesction converges linearly with rate 𝑆 = 2

1
b) If 𝑓 ′ (𝑟) ≠ 0, then secant converges superlinear 𝑓(𝑥) = 𝑥 4 − 2 ⇒ 𝑓 ′ (𝑥) = 4𝑥 3 ⇒ 𝑓′(24 ) ≠ 0. Secant
converges superlinear.
𝑥 1 1 3
c) For FPI: 𝑔(𝑥) = 2 + 𝑥 3 ⇒ 𝑔′ (𝑥) = 2 − 𝑥 4

1 1 3
𝑆 = |𝑔′ (24 )| = | − 1 | = 1
2
24
S isn’t less than 1, so FPI diverges.

d) Newton’s Method converges quadratically, so it is faster than Secant, FPI and Bisection method.

𝑓(𝑥) = 𝑥 4 − 2, 𝑓 ′ (𝑥) = 4𝑥 3 , 𝑓 ′ (1) = 4