MEIE6004: Advanced Numerical Methods
Root Finding Methods
Multivariable Problems
Nasser A. Al‐Azri
Introduction
Taylor’s Series for multivariable functions
Recall that Taylor’s series for a single‐variable function 𝑓 𝑥 , 𝑥 ∈ ℝ, is
𝑓 𝑥 ℎ 𝑓 𝑥 𝑓 𝑥 ℎ ⋯ (1)
! !
Consider the case of a multivariable function where we have n independent variables in the function, i.e., 𝑓 𝑋 , 𝑋 ∈
ℝ , as in the following example:
𝑓 𝑋 𝑓 𝑥 ,𝑥 ,𝑥 𝑥 𝑥 𝑥 (2)
Taylor’s series for such a function is given by:
𝑓 𝑋 𝐻 𝑓 𝑋 ℎ ℎ ⋯ ℎ ℎ ℎ ⋯ ℎ ℎ ℎ
! !
⋯ ℎ ⋯ (3)
Whereas X is the independent vector 𝑋 𝑥 ,𝑥 ,𝑥 ,…,𝑥 and H is the vector of increments in the different
directions i.e. 𝐻 ℎ ,ℎ ,ℎ ,…,ℎ .
Introduction
Newton’s Method
In case of the functions with one variable, the first derivative is interpreted as the rate of change (or gradient) of the
function at a point and in the neighborhood of that point, the first derivative represents the slope of the tangent and so
,as shown in figure (1), we can approach the zero by adding – which is the base of the triangle the separates xi
from xi+1. From this graph we can express xi+1 in terms of xi as given in equation (4) which represents Newton‐Raphson
method.
The convergence of Newton-Raphson Method
Introduction
Newton’s method is one of the most popular zero‐finding methods. For a single variable function i.e. 𝑓 𝑥 , 𝑥 ∈ ℝ, the
iterative equation of this method is
𝒇 𝒙𝒊
𝒙𝒊 𝟏 𝒙𝒊 (4)
𝒇 𝒙𝒊
This equation can be proven graphically or by using Taylor’s series approximation withℎ 𝑥 𝑥 and truncating after
two terms.
𝒇 𝒙𝒊 𝟏 𝟎 ≅ 𝒇 𝒙𝒊 𝒇 𝒙𝒊 𝒙𝒊 𝟏 𝒙𝒊 (5)
Solving for 𝑥 will result in equation (4).
The convergence of Newton-Raphson Method
Multivariate Root‐finding
Consider now a multivariable function, 𝑓 𝑋 , 𝑋 ∈ ℝ . Such as
𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 𝒙𝟐𝟏 𝒙𝟐 𝒙𝟑 (6)
Whereas 𝑋 ∊ ℝ , 𝑋 𝑥 ,𝑥 ,𝑥
Taylor’s series approximation based on equation (3) can be employed by truncating the second partial derivatives and
beyond. Hence,
𝝏𝒇 𝝏𝒇 𝝏𝒇 𝑻
𝒇 𝑿𝒊 𝟏 ≅ 𝒇 𝑿𝒊 , ,…, 𝑿𝒊 𝟏 𝑿𝒊 (7)
𝝏𝒙𝟏 𝝏𝒙𝟐 𝝏𝒙𝒏
For convenience, the first‐derivative terms are put in vector notation to accommodate the vectors 𝑋 and 𝑋 . Each
term in equation (7) will yield a scalar value. The third term is the dot product of the first‐derivative vector by the
difference vector.
Finding the zero of a function with n variables is a trivial problem as one can simply fix the numerical values of any (n‐1)
variables and then solve for the nth by using the single‐variable Newton’s method.
Multivariate Root‐finding
A better exploitation of this method is by using Taylor’s series for n equations with n variables. For example, consider the
case of finding the zero solution of three equations with three unknowns.
𝑓 𝑥 ,𝑥 ,𝑥 0 (8.a)
𝑔 𝑥 ,𝑥 ,𝑥 0 (8.b)
ℎ 𝑥 ,𝑥 ,𝑥 0 (8.c)
Using Taylor’s approximation similar to equation (7), with 𝑋 𝑥 𝑥 𝑥 ], will yield:
𝑓 𝑋 0≅𝑓 𝑋 , , 𝑋 𝑋 (9.a)
𝑔 𝑋 0≅𝑔 𝑋 , , 𝑋 𝑋 (9.b)
ℎ 𝑋 0≅𝑓 𝑋 , , 𝑋 𝑋 (9.c)
Multivariate Root‐finding
Putting all equations in a matrix format:
0 𝑓 𝑥 , ,𝑥 , ,𝑥 , 𝑥 , 𝑥 ,
0 ≅ 𝑔 𝑥 , ,𝑥 , ,𝑥 , . 𝑥 , 𝑥 ,
0 ℎ 𝑥 , ,𝑥 , ,𝑥 ,
𝑥 , 𝑥 ,
(10)
Now we can solve for 𝑋 𝑥 , 𝑥 , 𝑥 ,
Multivariate Root‐finding
𝑥 , 𝑥 , 𝑓 𝑥 , ,𝑥 , ,𝑥 ,
𝑥 , 𝑥 , 𝑔 𝑥 , ,𝑥 , ,𝑥 , (11)
𝑥 , 𝑥 , ℎ 𝑥 , ,𝑥 , ,𝑥 ,
A shorthand notation for equation (11) is
𝑋 𝑋 𝐽 .𝐹 𝑋 (12)
Whereas 𝐽 is the inverse of the Jacobian matrix (the matrix of the first partial derivatives) and 𝐹 𝑋 is the
vector 𝑓 𝑋 𝑔 𝑋 ℎ 𝑋 .
This equation represents Newton’s method for finding the root of a system of nonlinear equations.
Multivariate Root‐finding
Example 1
Find the zeros of the following set of nonlinear equations:
𝑓 𝑥 ,𝑥 𝑥 𝑠𝑖𝑛 𝑥 4 (13.a)
𝑓 𝑥 ,𝑥 𝑥 𝑥 10 (13.b)
Multivariate Root‐finding
Solution
Equation 12 can be used to find the solution of this set, i.e. to find 𝑋 𝑥 ,𝑥 at which 𝑓 𝑥 , 𝑥 𝑓 𝑥 ,𝑥 0. we
first need to define the function vector (F) and the Jacobian matrix (J).
𝑓 𝑥 ,𝑥 𝑥 𝑠𝑖𝑛 𝑥 4 sin 𝑥 𝑥 cos 𝑥
𝐹 𝑋 and 𝐽
𝑓 𝑥 ,𝑥 𝑥 𝑥 10 2 𝑥 𝑥 10 2 𝑥 𝑥 10
4 1.8239 0.5440 3.3563
Let’s start from 𝑋 for which 𝐹 𝑋 and 𝐽
10 16.0000 8.0000 8.0000
Multivariate Root‐finding
With the application of equation (12), we get
4 0.5440 3.3563 1.8239 0.9646
𝑋 𝑋 𝐽 .𝐹 𝑋
10 8.0000 8.0000 16.0000 11.0354
From here on, we keep repeating the same procedure until we get to the desired accuracy of the solution as
shown in the table.
i 𝑋 𝑥 ,𝑥 𝐹 𝑓 ,𝑓
0 [-4.0000, -10.0000] [1.8239, 16.0000]
1 [-0.9646, -11.0354] [3.0362, 4.0000] so we can take:
2 [-3.8535, -7.1465] [6.9286, 1.0000]
3 [-7.1072, -3.3928] [2.2334, 0.2500] 𝑥 6.1515 𝑎𝑛𝑑
4 [-6.5113, -3.7387] [0.3388, 0.0625]
𝑥 3.8495
5 [-6.3014, -3.8236] [0.0280, 0.0156]
6 [-6.2231, -3.8394] [0.0015, 0.0039] as a solution at which
7 [-6.1866, -3.8446] [0.2001, 0.9766]*10-3 the two functions are
8 [-6.1685, -3.8471] [0.0478, 0.2441]*10-3
less than 10‐5 , which is
9 [-6.1594, -3.8484] [0.1192, 0.6104]*10-4
10 [-6.1549, -3.8490] [0.0298, 0.1526]*10-4 almost zero.
11 [-6.1526, -3.8493] [0.0744, 0.3815]*10-5
12 [-6.1515, -3.8495] [0.1860, 0.9537]*10-6
Multivariate Root‐finding
Example 2
Find the solution 𝑥, 𝑦, 𝑤 that satisfies the following set of nonlinear
equations.
𝑓 𝑥, 𝑦, 𝑤 𝑥 𝑦𝑤=2 (14.a)
𝑔 𝑥, 𝑦, 𝑤 𝑥𝑦𝑤 𝑥 𝑤 =6 (14.b)
ℎ 𝑥, 𝑦, 𝑤 𝑥 𝑦 𝑤 =7 (14.c)
Multivariate Root‐finding
Solution
This system of nonlinear equations can be solved using Newton’s method by modifying it to a zero‐finding problem.
𝑓 𝑥, 𝑦, 𝑤 𝑥 𝑦𝑤‐2=0 (15.a)
𝑔 𝑥, 𝑦, 𝑤 𝑥𝑦𝑤 𝑥 𝑤 ‐6=0 (15.b)
ℎ 𝑥, 𝑦, 𝑤 𝑥 𝑦 𝑤 ‐7=0 (15.c)
hence
𝑥 𝑦𝑤 2 2𝑥 𝑤 𝑦 𝑥
𝐹 𝑥𝑦𝑤 𝑥 𝑤 6 and J= 𝑦𝑤 2𝑥 𝑥𝑤 𝑥𝑦 2𝑤 and let 𝑉 𝑦
𝑥 𝑦 𝑤 7 2𝑥 2𝑦 2𝑤 𝑤
Newton’s iterative equation (12) will be:
𝑉 𝑉 𝐽 𝐹
Multivariate Root‐finding
1 0 2 1 1
Let’s start with 𝑉 1 for which we will get 𝐹 3 and 𝐽 3 1 3 and using the iterative equation we will
1 4 2 2 2
get:
1 2 1 1 0 1
𝑉 1 3 1 3 3 2.5
1 2 2 2 4 3.5
And then we continue until the solution converges. The iterations followed are shown in the following table:
Multivariate Root‐finding
i 𝑉 𝑥, 𝑦, 𝑤 𝐹 𝑓, 𝑔, ℎ
0 [1.0000, 1.0000, 1.0000] [0, ‐3, ‐4]
1 [‐1.0000, 2.5000, 3.5000] [7.7500, ‐1.5000, 12.5000]
2 [‐2.1110, ‐0.2500, 3.3611] [1.6165, 11.5278, 8.8164]
3 [‐1.4700, 0.0082, 2.4715] [0.1813, 2.2392, 1.2692]
4 [‐1.1836, 0.2759, 2.3842] [0.0587, 0.3066, 0.1613]
5 [‐1.0987, 0.3354, 2.3856] [0.0073, 0.0192, 0.0107]
6 [‐1.0904, 0.3399, 2.3865] [0.0735, 0.1571, 0.0902]*10‐3
7 [‐1.0903, 0.3399, 2.3866] [0.0639, 0.1297, 0.0755]*10‐7
8 [‐1.0903, 0.3399, 2.3866] [0.0000, 0.0000, 0.0000]
So with this result, we get the solution of the system:
𝑓 𝑥, 𝑦, 𝑤 𝑥 𝑦𝑤=2
𝑔 𝑥, 𝑦, 𝑤 𝑥𝑦𝑤 𝑥 𝑤 =6
ℎ 𝑥, 𝑦, 𝑤 𝑥 𝑦 𝑤 =7
to be x=‐1.0903, y=0.3399 and w=2.3866.
Programming Task …
Code the Multivariate Root-finding
method in Matlab.
Multivariate Numerical
Differentiation
The same system of equations can be more numerically
handled by using numerical differentiation:
𝜕𝑓 𝜕𝑓 𝜕𝑓
𝜕𝑥 𝜕𝑥 𝜕𝑥
𝑥 , 𝑥 , 𝑓 𝑥 , ,𝑥 , ,𝑥 ,
𝜕𝑔 𝜕𝑔 𝜕𝑔
𝑥 , 𝑥 , 𝑔 𝑥 , ,𝑥 , ,𝑥 ,
𝑥 𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥
, , ℎ 𝑥 , ,𝑥 , ,𝑥 ,
𝜕ℎ 𝜕ℎ 𝜕ℎ
𝜕𝑥 𝜕𝑥 𝜕𝑥
𝜕𝑓 𝑓 𝑥 ∈ 𝑓 𝑥 ∈ 𝜕𝑔 𝑔 𝑥 ∈ 𝑔 𝑥 ∈ 𝜕ℎ ℎ 𝑥 ∈ ℎ 𝑥 ∈
≅ ≅ ≅
𝜕𝑥 2∈ 𝜕𝑥 2∈ 𝜕𝑥 2∈
Multivariate Root‐finding
Exercises
1. Find a solution 𝑋 𝑥 ,𝑥 ,𝑥 for the following system of nonlinear equations:
𝑓 𝑥 ,𝑥 ,𝑥 𝑥 𝑥 𝑥 77
𝑓 𝑥 ,𝑥 ,𝑥 𝑥 𝑥 𝑥 𝑥 𝑥 𝑥 26
𝑓 𝑥 ,𝑥 ,𝑥 𝑥 𝑥 𝑥 120
Summary
