Private Higher School of Engineering and Technology
Numerical Analysis
Tutorial 1 : Numerical solutions of linear systems
Solutions
Level : 3A & 3B
Exrecise 1 :
We are given :
f (x) = ex − 2x − 2, on I = [1, 2]
1. Uniqueness of solution
We check that f is continuous on [1, 2] :
f (1) = e1 − 2(1) − 2 = e − 4 ≈ −1.28 < 0f (2) = e2 − 4 − 2 = e2 − 6 ≈ 7.39 − 6 = 1.39 > 0
So, by the Intermediate Value Theorem, ∃x∗ ∈ (1, 2) such that f (x∗ ) = 0.
Also, since f ′ (x) = ex − 2 > 0 for x ∈ [1, 2], f is strictly increasing → uniqueness of the root.
2. Bisection method iteration count
Bisection stops when :
b−a 1
< ε ⇒ n < 0.01 ⇒ 2n > 100 ⇒ n > log2 100 ≈ 6.64
2n 2
So we need n = 7 iterations.
3. Bisection Iterations
Initial interval : [1, 2].
— c0 = 1+2 2 = 1.5, f (1.5) = e
1.5 − 3 − 2 ≈ 4.48 − 5 = −0.52
1.5+2
— c1 = 2 = 1.75, f (1.75) ≈ 5.75 − 5.5 = 0.25
— c2 = 1.5+1.75
2 = 1.625, f (1.625) ≈ 5.08 − 3.25 − 2 = −0.17
4. Fixed Point Functions
We want : f (x) = 0 ⇐⇒ ex − 2x − 2 = 0 ⇒ ex = 2x + 2.
ex − 2
Then : x = g1 (x) = ln(2x + 2) and x = g2 (x) =
2
1
5. Fixed Point Convergence
Check derivative for g1 (x) = ln(2x + 2) :
2 1
g1′ (x) = = , x ∈ [1, 2] ⇒ g1′ (x) ∈ [0.5, 1]
2x + 2 x+1
So |g1′ (x)| ≤ 1, not strictly ¡ 1 → no guaranteed convergence.
x
For g2 (x) = e 2−2 :
ex e
g2′ (x) = , g2′ (1) = ≈ 1.36 > 1
2 2
→ Diverges.
6. Newton’s Method Iteration
f (xn ) exn − 2xn − 2
xn+1 = xn − = x n −
f ′ (xn ) exn − 2
7. Good Initial Guess
Choose x0 where f ′ (x0 ) ̸= 0 and near root → x0 = 1.5
8. First Two Newton Iterations
Let’s use x0 = 1.5 :
−0.52
f (1.5) = e1.5 −2(1.5)−2 ≈ 4.48−3−2 = −0.52f ′ (1.5) = e1.5 −2 ≈ 4.48−2 = 2.48x1 = 1.5− ≈ 1.7097
2.48
Now for x1 = 1.7097 :
f (1.7097) ≈ e1.7097 − 2(1.7097) − 2 ≈ 5.53 − 3.42 − 2 = 0.11f ′ (1.7097) ≈ e1.7097 − 2 = 5.53 − 2 = 3.53
0.11
x2 = 1.7097 − 3.53 ≈ 1.6785
Exercise 2
Given :
f (x) = x3 + 3x − 3 on I = [0, 1]
1. Existence and Uniqueness of Solution
Check endpoints :
f (0) = −3 < 0, f (1) = 1 + 3 − 3 = 1 > 0
Since f is continuous and strictly increasing (because f ′ (x) = 3x2 + 3 > 0), there is a unique
x∗ ∈ (0, 1) such that f (x∗ ) = 0.
2
2. Fixed Point Function
We are given :
3
g(x) = ⇒ f (x) = x3 + 3x − 3 = 0 ⇐⇒ g(x) = x
x2 +3
3a. Lipschitz Condition
We compute :
′ d 3 6x 6x
g (x) = 2
=− ⇒ |g ′ (x)| =
dx x +3 (x2 + 3) 2 (x + 3)2
2
On [0, 1], maximum occurs at x = 1 :
6 6 3 2
|g ′ (1)| = = = = 0.375 <
(12 + 3) 2 16 8 3
So |g ′ (x)| ≤ 2
3 holds.
3b. Convergence of Fixed-Point Method
Since |g ′ (x)| ≤ M0 < 1, by Banach’s fixed point theorem, the sequence converges to x∗ .
3c. Estimate Iterations
Use :
M0n 2
|xn − x∗ | ≤|x1 − x0 |, where M0 = , ε = 10−3
1 − M0 3
Let’s assume |x1 − x0 | ≤ 0.5 (safe upper bound), then :
(2/3)n (2/3)n 10−3
· 0.5 ≤ 10−3 ⇒ · 0.5 ≤ 10−3 ⇒ (2/3)n ≤ ≈ 6.67 × 10−4
1 − 2/3 1/3 1.5
log(6.67 × 10−4 )
n ≥ log2/3 (6.67 × 10−4 ) ≈ ≈ 15.8 ⇒ n0 = 16
log(2/3)
3d. First 3 Iterations with x0 = 0.5
3 3 3 3
x0 = 0.5x1 = g(0.5) = = ≈ 0.9231x2 = g(0.9231) ≈ 2
≈ ≈ 0.7791
0.25 + 3 3.25 (0.9231) + 3 3.8521
3 3
x3 = g(0.7791) ≈ 0.606+3 = 3.606 ≈ 0.832
4a. Bisection Iteration Estimate
Initial interval : [0, 1], error bound :
1
< 10−3 ⇒ n > log2 (1000) ≈ 9.97 ⇒ n1 = 10
2n
3
4b. Explanation
Fixed-point method requires 16 iterations ; bisection only needs 10 → Bisection is more efficient
in this case because the contraction constant M0 is close to 1.
4c. First 3 Bisection Iterations
a = 0, b = 1c0 = 0.5, f (0.5) = 0.125+1.5−3 = −1.375c1 = 0.75, f (0.75) = 0.422+2.25−3 = −0.328
c2 = 0.875, f (0.875) = 0.67 + 2.625 − 3 = 0.295
5a. Better Estimate of |g ′ (x)|
6x
|g ′ (x)| = , maximize over x ∈ [0, 1]
(x2 + 3)2
Maximum occurs at x = 1 :
6 6 3
M1 = = =
(12 + 3)2 16 8
5b. New Iteration Count with M1 = 3/8
Repeat convergence bound :
(3/8)n (3/8)n
· 0.5 ≤ 10−3 ⇒ · 0.5 ≤ 10−3 ⇒ (3/8)n ≤ 0.00125 ⇒ n2 ≈ 8.2 ⇒ n2 = 9
1 − 3/8 5/8
5c. Is n2 the Minimum ?
Not necessarily. n2 is based on worst-case estimation of |g ′ (x)|. The actual convergence may be
faster depending on initial guess and local contraction.
Exercise 3
Given : h πi
f (x) = cos(x) − 3x on I = 0,
3
1. Uniqueness of the Solution
Check :
π π
f (0) = cos(0) − 0 = 1 > 0f = cos − π ≈ 0.5 − 3.14 ≈ −2.64 < 0
3 3
So, by the Intermediate Value Theorem, there exists x∗ ∈ 0, π3 such that f (x∗ ) = 0.
Also : h πi
′
f (x) = − sin(x) − 3 < 0 on 0,
3
→ f (x) is strictly decreasing → the solution is unique.
4
2. Bisection Iteration Estimate
We want :
π π 3.1416
n
< 10−3 ⇒ 2n > −3
≈ ≈ 1047.2 ⇒ n ≥ ⌈log2 1047.2⌉ ≈ 11
3·2 3 · 10 0.003
3. Bisection Method (to ε = 10−3 )
Start with interval [a = 0, b = π3 ≈ 1.047].
— c0 = 0+1.047
2 = 0.5235, f (c0 ) = cos(0.5235) − 3 · 0.5235 ≈ 0.866 − 1.570 ≈ −0.704
— c1 = 0+0.5235
2 = 0.26175, f (c1 ) ≈ cos(0.26175) − 3 · 0.26175 ≈ 0.965 − 0.785 ≈ 0.18
0.26175+0.5235
— c2 = 2 ≈ 0.3926, f (c2 ) ≈ cos(0.3926) − 3 · 0.3926 ≈ 0.924 − 1.178 ≈ −0.254
— Continue until error < 10−3
After about 11 iterations, you get a value for x∗ such that |f (x∗ )| < 10−3 .
4. Fixed-Point Iteration
We are given :
cos(xn )
xn+1 = g(xn ) =
3
4a. Convergence Verification
Let :
′ d cos(x) sin(x) | sin(x)|
g (x) = =− ⇒ |g ′ (x)| =
dx 3 3 3
√
On [0, π3 ], max | sin(x)| = sin π3 = 23 ≈ 0.866
0.866
⇒ max |g ′ (x)| = ≈ 0.288 < 1
3
So the sequence converges.
4b. First Four Iterations with x0 = 0
cos(0) 1 cos(0.3333) 0.9455 cos(0.3152) 0.949
x0 = 0x1 = = ≈ 0.3333x2 = ≈ ≈ 0.3152x3 = ≈ ≈ 0.3163
3 3 3 3 3 3
cos(0.3163)
x4 = 3 ≈ 0.9486
3 ≈ 0.3162 → Converging to x∗ ≈ 0.3162
5. Newton’s Method
5a. Iterative Scheme
Given :
f (xn ) cos(xn ) − 3xn
f (x) = cos(x) − 3x, f ′ (x) = − sin(x) − 3 ⇒ xn+1 = xn − ′
= xn −
f (xn ) − sin(xn ) − 3
5
5b. Good Initial Value
Choose x0 near the fixed-point result → x0 = 0.3
5c. Newton Iterations
x0 = 0.3f (x0 ) = cos(0.3) − 0.9 ≈ 0.955 − 0.9 = 0.055
f’(x0 ) = − sin(0.3) − 3 ≈ −0.2955 − 3 = −3.2955
0.055
x1 = 0.3 − −3.2955 ≈ 0.3167 Next :
f (x1 ) ≈ cos(0.3167) − 3 · 0.3167 ≈ 0.949 − 0.950 = −0.001
f’(x1 ) ≈ − sin(0.3167) − 3 ≈ −0.311 − 3 = −3.311
x2 = 0.3167 − −0.001
−3.311 ≈ 0.3162
→ Converges quickly to x∗ ≈ 0.3162 with accuracy < 10−3 .
Exercise 4
We are given the equation :
f (x) = x3 and we want to solve : f (x) = 1 − x on [0, 1]
1. Uniqueness of the Solution
Define :
f (x) = x3 − (1 − x) = x3 + x − 1
We analyze this new function :
f (0) = 0 + 0 − 1 = −1 < 0, f (1) = 1 + 1 − 1 = 1 > 0
Since f is continuous on [0, 1], by the Intermediate Value Theorem, there exists x∗ ∈ (0, 1) such
that f (x∗ ) = 0.
Also, the derivative :
f ′ (x) = 3x2 + 1 > 0 on [0, 1] ⇒ strictly increasing ⇒ only one root
2. Bisection Method – Number of Iterations
To find x∗ such that |f (x∗ )| < 10−3 :
Initial interval length L = 1.
We need :
1
< 10−3 ⇒ 2n > 1000 ⇒ n > log2 (1000) ≈ 9.97 ⇒ n = 10
2n
6
3. Newton’s Method
a) Iterative Scheme and Initial Guess
We define :
f (x) = x3 − (1 − x) = x3 + x − 1, f ′ (x) = 3x2 + 1
Newton’s iteration :
f (xn ) x3n + xn − 1
xn+1 = xn − = x n −
f ′ (xn ) 3x2n + 1
We choose x0 = 0.5 (in the middle of the interval and likely to converge).
b) First Iterations to Reach ε = 10−3
−0.375
x0 = 0.5, f (0.5) = 0.125+0.5−1 = −0.375, f ′ (0.5) = 3(0.25)+1 = 1.75 ⇒ x1 = 0.5− ≈ 0.7143
1.75
Next :
0.0783
f (0.7143) ≈ 0.364+0.7143−1 = 0.0783, f ′ (0.7143) = 3(0.7143)2 +1 ≈ 2.53 ⇒ x2 = 0.7143− ≈ 0.6833
2.53
Next :
0.0023
f (0.6833) ≈ 0.319 + 0.6833 − 1 = 0.0023, f ′ (0.6833) ≈ 2.4 ⇒ x3 = 0.6833 − ≈ 0.6824
2.4
Next :
f (0.6824) ≈ 0.68243 + 0.6824 − 1 ≈ 0.0001 ⇒ accuracy < 10−3
So, solution x∗ ≈ 0.6824 found in 4 iterations.
