CVEN2002 Study Notes
Numerical Methods
MATHEMATICAL MODELLING
• Before computers, engineers could only solve problems using exact
solutions, graphical solutions or through tedious calculations
• Modern computing technology has allowed for numerical methods,
providing great accuracy and calculation efficiency
• The following are examples of mathematical modelling often undertaken:
o Ordinary differential equations in the form (dy/dt = f(t,y)) can be
approximated using: y1 = y0 + f(t,y)
o The velocity of a falling object could be calculated analytically
(exactly) using multiple formulae or simply using the above
approximation
• In most mathematical models, a dependant variable becomes a function of
various independent variables, parameters and constraints
• The Euler Method demonstrates that: New Value = Old Value + Step
Size*Slope
TAYLOR SERIES
• The Taylor Series exemplifies the Euler Method by approximating the
value of a function by the sum of its derivatives
• A zero-order approximation could be made by assuming that the value
of the new point is the same as that at the old function point
• The Euler Method as described above is a first-order approximation
through the inclusion of a first derivative
• The Taylor Series can be equated exactly to the actual function by
including a truncating error (R)
o The size of the truncating error is proportional to the step-size
raised to the (n+1)th power
ROOTS OF EQUATIONS
• Certain equations have no analytical (exact) solution, so we can
approximate the root via the graphical method
• The bisection method is commonly used in numerical methods to create
an approximate bracket for the root of an equation
o Two points of opposite signs are taken and the root is deemed to
be along the interval joining these two points
o The two points must fulfil the following inequality: f1*f2 < 0
o The root can be estimated as: fr = (f1+f2)/2 for each iteration
o If fr*f1<0, then the root lies in the lower subinterval and the
process can be reiterated (and vice versa)
o Computers undertake an incremental search to narrow down the
root bracket until it is sufficiently approximate
• The bisection method would be undertaken by the program until the
error is sufficiently low: error %= abs((xnew-xold)/xnew)
• The bisection method is an example of a bracketing method, whereas we
can also use an open method requiring just one point
, o The most commonly used open method is the Newton-Raphson
method
o x1 = x0 – f(x0)/f’(x0)
o This method involves taking a tangent from a single function point
and then observing if the function value at the root of the tangent
converges or diverges towards the root of the function
o The error on each iteration of the Newton-Raphson method is
approximately proportional to the square root of the previous
error
o This is helpful for finding approximations to roots that cannot be
solved analytically
• The Newton-Raphson method is essentially a first-order Taylor series
• There are however a few pitfalls of the Newton-Raphson method:
o This open method tends to perform poorly in situations with
multiple roots or multiple stationary points
o The need to differentiate the function can create problems
• The secant method is another open method which does not require
differentiation
o Backward finite divided difference equates to: f(x0) ~= (f(x0)-
f(x1))/(x0-x1) and forward finite divided difference is the opposite
o Hence the secant formula is the same as that for the Newton-
Raphson method, except backward or forward difference is used to
replace the differential
ROOTS OF POLYNOMIALS
• A polynomial is a function consisting of a certain number of
degrees/terms
• Polynomials can be involved with ordinary differential equations of given
orders
• A second order ODE can be expressed in terms of a set of first order ODE’s
and so on, through the introduction of a new variable (z=dy/dt)
o When we introduce a general solution of y=e^(rt), the ODE can be
expressed as a polynomial (characteristic equation)
• Muller’s method uses three known points of a function to estimate the
root through the superimposition of a parabola
o Root estimation = x2 -2c/(b+-sqrt(b2-4ac))
• Bairstow’s method involved formatting a polynomial into a factored
form so that its roots are easily determined
o After guessing a value of the root, the polynomial is divided by ‘x-
x1’ and a remainder of zero would prove that ‘x1’ is a root of the
function
o Bairstow established several relationships between the original
function and the function once divided by ‘x-x1’:
§ b n = an
§ bi = ai + bi*x2
MATRIX THEORY
• A matrix is symmetric if aij = aji
Numerical Methods
MATHEMATICAL MODELLING
• Before computers, engineers could only solve problems using exact
solutions, graphical solutions or through tedious calculations
• Modern computing technology has allowed for numerical methods,
providing great accuracy and calculation efficiency
• The following are examples of mathematical modelling often undertaken:
o Ordinary differential equations in the form (dy/dt = f(t,y)) can be
approximated using: y1 = y0 + f(t,y)
o The velocity of a falling object could be calculated analytically
(exactly) using multiple formulae or simply using the above
approximation
• In most mathematical models, a dependant variable becomes a function of
various independent variables, parameters and constraints
• The Euler Method demonstrates that: New Value = Old Value + Step
Size*Slope
TAYLOR SERIES
• The Taylor Series exemplifies the Euler Method by approximating the
value of a function by the sum of its derivatives
• A zero-order approximation could be made by assuming that the value
of the new point is the same as that at the old function point
• The Euler Method as described above is a first-order approximation
through the inclusion of a first derivative
• The Taylor Series can be equated exactly to the actual function by
including a truncating error (R)
o The size of the truncating error is proportional to the step-size
raised to the (n+1)th power
ROOTS OF EQUATIONS
• Certain equations have no analytical (exact) solution, so we can
approximate the root via the graphical method
• The bisection method is commonly used in numerical methods to create
an approximate bracket for the root of an equation
o Two points of opposite signs are taken and the root is deemed to
be along the interval joining these two points
o The two points must fulfil the following inequality: f1*f2 < 0
o The root can be estimated as: fr = (f1+f2)/2 for each iteration
o If fr*f1<0, then the root lies in the lower subinterval and the
process can be reiterated (and vice versa)
o Computers undertake an incremental search to narrow down the
root bracket until it is sufficiently approximate
• The bisection method would be undertaken by the program until the
error is sufficiently low: error %= abs((xnew-xold)/xnew)
• The bisection method is an example of a bracketing method, whereas we
can also use an open method requiring just one point
, o The most commonly used open method is the Newton-Raphson
method
o x1 = x0 – f(x0)/f’(x0)
o This method involves taking a tangent from a single function point
and then observing if the function value at the root of the tangent
converges or diverges towards the root of the function
o The error on each iteration of the Newton-Raphson method is
approximately proportional to the square root of the previous
error
o This is helpful for finding approximations to roots that cannot be
solved analytically
• The Newton-Raphson method is essentially a first-order Taylor series
• There are however a few pitfalls of the Newton-Raphson method:
o This open method tends to perform poorly in situations with
multiple roots or multiple stationary points
o The need to differentiate the function can create problems
• The secant method is another open method which does not require
differentiation
o Backward finite divided difference equates to: f(x0) ~= (f(x0)-
f(x1))/(x0-x1) and forward finite divided difference is the opposite
o Hence the secant formula is the same as that for the Newton-
Raphson method, except backward or forward difference is used to
replace the differential
ROOTS OF POLYNOMIALS
• A polynomial is a function consisting of a certain number of
degrees/terms
• Polynomials can be involved with ordinary differential equations of given
orders
• A second order ODE can be expressed in terms of a set of first order ODE’s
and so on, through the introduction of a new variable (z=dy/dt)
o When we introduce a general solution of y=e^(rt), the ODE can be
expressed as a polynomial (characteristic equation)
• Muller’s method uses three known points of a function to estimate the
root through the superimposition of a parabola
o Root estimation = x2 -2c/(b+-sqrt(b2-4ac))
• Bairstow’s method involved formatting a polynomial into a factored
form so that its roots are easily determined
o After guessing a value of the root, the polynomial is divided by ‘x-
x1’ and a remainder of zero would prove that ‘x1’ is a root of the
function
o Bairstow established several relationships between the original
function and the function once divided by ‘x-x1’:
§ b n = an
§ bi = ai + bi*x2
MATRIX THEORY
• A matrix is symmetric if aij = aji
