THE KENYA METHODIST UNIVERSITY

P.O. Box 267

MERU
MATHS 320: NUMERICAL ANALYSIS 1
Course Instructor: Winifred Mutuku
Department of Pure and Applied Sciences.
2
MATHS 320: NUMERICAL ANALYSIS 1
INTRODUCTION
This course will introduce the students to the general concepts and skills of mathematics
essential for application in problem solving and computational disciplines.
COURSE OBJECTIVES
During the course, the undergraduate student will be able to:
- Understand the algebra of the number systems, introduction to errors, sources of
errors and propagation of errors.
- Use Taylors series and Lagranges Interpolation to reconstruct the function f(x)
and determine the root of a function f(x) = 0 by bisection method, Secant,
Newton-Raphson and False-position methods.
- Interpolation based on finite difference operators; forward, backward and central
and form their respective difference tables.
- Understand the concept of Lagrange and Newton interpolation, find an
approximate value by Lagrange Interpolation; find unique polynomial by
Lagrange interpolation and Newton divided difference.
- State and use the least squares and Chebychevs approximations
- Know the various numerical methods used to find derivative of a function f(x)
like methods based in interpolation, finite differences and undetermined
coefficient. Extrapolation to the limit.
1
COURSE CONTENT
- Number System.
- Introduction to errors
- Lagrange interpolation
- Finite difference
- Interpolation based on finite differences.
- Least square approximations
- Chebychevs approximations
- Numerical differentiation.
- Extrapolation to the limit.
2
TEACHING AND LEARNING METHODS
Lecture method consisting of stating, illustrating, proving various numerical
methods. Application of these methods are given by use of examples.
Questions and answer method.
Tutorials in which problem solving techniques and general discussion are
conducted regularly.
Tests and assignments are continuously given to test students progress and
understanding and discussed together after grading.
STUDENTS ASSESSMENT
Assignment
Course Examination
Individual students marks of these assignments will contribute to the final examination
mark and grade for the course.
3
COURSE OUTLINE FOR THE TRIMESTER
WEEK 1 and 2
Number Systems
WEEK 3
Approximations and errors
WEEK 4
Lagrange interpolation
WEEK 5 and 6
Finite difference
Interpolation based on finite differences.
WEEK 7
Least square approximations
WEEK 8
Chebychevs approximations
WEEK 9 and 10
Numerical differentiation.
WEEK 11 and 12
4
Extrapolation to the limit.
WEEK 13 and 14
Assignments
Course Examinations
LEARNING RESOURCES
Hilderbrand, F.B: Introduction to Numerical Analysis; 2
nd
Edition, McGraw-Hill, Inc.,
1991.
Hultquist, P.F.: Numerical Methods for Engineers and Scientists; Benjamin/Cummings
Publishing Company, Inc., 1988
Germund, D.; Numerical Methods; Prentice-Hall, Inc., 1974
5
Students Learning Objectives
WEEK 1 and 2
1) State the various number systems
2) Perform the basic operation of the different number systems
3) Convert between different number system
4) Represent data using floating point and fixed point methods.
5) Evaluate the complement of denary and binary number systems and use them to
perform subtraction of numbers.
Introduction
Numerical analysis or computing is an approach for solving complex mathematical
problems using only simple arithmetic operations. It involves formulation of
mathematical models of physical situations that can be solved with arithmetic operations.
It can be used in the following areas.
i. Finding roots of equations
ii. Solving systems of linear algebraic equations.
iii. Interpolation and regression analysis.
iv. Numerical integration.
v. Numerical differentiation.
vi. Solution of differential equations
vii. Boundary value problems
viii. Solution of matrix problems.
6
NUMBER SYSTEMS
There are different number systems depending on the base/radix. The number systems are
1. Decimal Number System
2. Binary Number System
3. Octal Number System
4. Hexadecimal Number System
5. Duodecimal Number System
Decimal Number System
This is also known as denary number system. It has 10 digits/symbols; 0, 1, 2, ., 9.
The digits are 10, hence its base is 10. Every number in the system is interpreted as a sum
of multiples of integer powers of 10.
For example,
1.
( )
10
4987
= 4 x 10
3
+ 9 x 10
2
+ 8 x 10
1
+ 7 x 10
1
2.
( )
3 2 1 0 1 2
10
10 5 10 0 10 1 10 2 10 4 10 3 105 . 342

+ + + + +
The expanded notation for the integer part of a decimal number is

m
i
i
i
d N
0
10
Where
i
d
is the decimal digits 0, 1, 2, , 9 and m is the number of digits.
The fractional part of a decimal number is represented as

n
i
i
i
d
1
10
, where n is the number of digits in the fractional part.
7
BINARY NUMBER SYSTEM
The binary number system has a base of 2 with digits 0 and 1. These digits/symbols are
known as bits. It is represented as a sum of multiples of integer powers of 2.
For example,
i.
( )
2 1 0 1 2 3
2
2 1 2 1 2 1 2 0 2 1 2 1 11 . 1101

+ + + + +
In general, the integer part of a binary number can be written as

+ + +
m
i
i
i
m
m
m
m
d d d d
0
0
0
1
1
2 2 ....... .......... 2 2
, where i
d
are the binary
symbols/digits 0 and 1.
This can be generalized to any base b as;

m i
i
i
b d , where b is an integer greater than 1 and digits
i
d
are between
0 and b-1.
Note: the base is also called radix and the fractional point is called the radix point.
Exercise
Convert
( )
2
101 . 1011
to denary number system.
HEXADECIMAL NUMBER SYSTEM
The base to the hexadecimal number system is 16 and the digits/symbols used are 0, 1, 2,
..9 and A, B, C, .., F. The letters A to F represent the digits 10, 11,. To 15
respectively. The hexadecimal number system is a sum of multiples of integer powers of
16.
For example,
8

( )
2 1 0 1
16
16 7 16 1 16 12 16 10 17 .

+ + + AC

( )
10
0898438 . 172
Exercise
1. Convert the following hexadecimal numbers to Denary number system
a.
( )
16
2 3 . 7 2 E A
b.
( )
16
21 . 4 3 F C
Converting Binary Number to Hexadecimal
i. Group the binary digits in sets of four
ii. Convert each group to its equivalent.
Example
Convert
( )
2
0100100001 0111101000
to hexadecimal number system
Solution
0111 1010 0001 0010 0001
0111 = 7 2 1 2 1 2 1 2 0
0 1 2 3
+ + +
Similarly,
1010 = 10 = A
0001 = 1
0010 = 2
0001 = 1
Thus
( ) ( )
16 2
121 7 0100100001 0111101000 A

9
OCTAL NUMBER SYSTEM
The octal number system has 8 digits and hence is of base 8. The digits /symbols are 0, 1,
2, , 7. Any number is a sum of multiples of integer powers of 8.
Example
( ) ( )
10
0 1 2 3
8
1070 8 6 8 5 8 0 8 2 2056 + + +
Question
Convert the following Octal numbers into their denary equivalent
a)
( )
8
321 . 357
b)
( )
8
452 . 263
Converting Binary Number to Octal
a) Group the binary digits into sets of 3
b) Convert each set to its denary equivalent.
Example
Convert
( )
2
1011010
to octal number system
Solution
001 011 010
001 = 1 2 1 2 0 2 0
0 1 2
+ +
Similarly,
011 = 3
010 = 2
Thus
( ) ( )
8 2
132 1011010
10
DUODECIMAL NUMBER SYSTEM
The duodecimal number system has 12 symbols/digits.The digits are 0, 1, 2,.., 9 and X
and . The last 2 symbols represent 10 and 11 respectively. The duodecimal number
system is a sum of multiples of integer powers of 12.
Example
( )
3 2 1 0 1 2
12
12 6 12 3 12 1 12 5 12 10 12 2 136 . 5 2

+ + + + +

( )
10
108 . 413
288
1
48
1
12
1
5 120 288 + + + + +
Question
Convert
( )
12
265 . 4 3
to its denary equivalent.
Exercise
Express the following numbers in denary number system.
a)
( )
12
11 . 11001
b)
( )
8
143 . 776
c)
( )
12
5 2 . 9 4
d)
( )
16
5 3 . 8 6 D F
CONVERSION OF NUMBERS
Non-Decimal System to Decimal Systems
The following algorithm is used to convert numbers in base2, base8, base 12 and base16
to a decimal number.
Integer Part
11
1. Multiply the left most digit by the base b.
2. Add the next digit to the right to the product.
3. Multiply the sum by the base and add the next digit.
4. Continue the process until the last (right most) digit is added.
The sum is the decimal equivalent of the given integer number.
Fractional Part.
1. Multiply the right most digit by b
-1
.
2. Add the next digit to the left to the product.
3. Multiply the sum by b
-1
and add the next digit.
4. Continue the process until the last (left most) digit in the fractional part is added.
The product is the decimal equivalent of the given fractional number.
Example.
1. Convert
( )
2
1101 . 1101
to its decimal equivalent.
Solution
Integer Part
1 1 0 1
1x2=2
2+1=3x2
6+0= 6x2
12+1 = 13
Decimal part
1 1 0 1
12
1x2
-1
=05
0.5+0 = 0.5x2
-1
=0.25
0.25+1=1.25x2
-1
=0.625
0.625+1=1.625x2
-1
=0.8125
Thus
( ) ( )
10 2
8125 . 13 1101 . 1101
2. Convert
( )
16
12 AF
to its denary equivalent.
Solution
1 2 A F
1 x 16 = 16
16 + 2 = 18 x 16 = 288
288 + 10 = 298 x 16 = 4768
4768 + 15 = 4783
Thus
( ) ( )
10 16
4783 12 AF
Exercise
1. Convert the following numbers to denary number system.
a.
( )
8
121 . 357
b.
( )
12
136 . 245
c.
( )
2
1011 . 11011
d.
( )
16
8 2 . 5 4 B C
13
Denary System to Non-Denary Systems.
The following algorithm is used to convert numbers in denary number system to base2,
base8, base 12 and base16.
Integer Part
1. Divide the integer part by the base b of the new system. The remainder will
constitute the right digit of the integer part of the new number.
2. Divide the quotient again by the base b. the remainder is the 2
nd
digit from the
right.
3. Continue the process until zero quotients is obtained. The last remainder is the left
most digit of the new number.
Example 1
Change
( )
10
245
to binary.

Thus
( ) ( )
2 10
11110101 245
Solution
2 245
2
1221
2
610
2
30 1
2
150
2
71
2
31
2
11
2
01
14
Example 2
Convert
( )
10
524
to octal.
Solution
8 524
8
65 4
8
81
8
10
8
01
Thus
( ) ( )
8 10
1014 524
Question
Convert
( )
10
897
to duodecimal.
Fractional part
1. Multiply the fractional part of the decimal number by the base b of the new
system. The integral part of the product constitutes the left most digit of the
fractional part of the new number.
2. Multiply the fractional part of the product by the base. The integral part of the
resultant product is the 2
nd
digit from the left.
3. Continue the process until a zero fractional part occurs. The integer part of the last
product will be the right most digit of the fractional part of the new number.
15
Example
1) Change
( )
10
526 . 0
octal.
Solution
0.526 x 8 = 4.208
0.208 x 8 = 1.664
0.664 x 8 = 5.312
0.312 x 8 = 2.496 and so on.
Thus the number
( ) ( )
8 10
4152 . 0 526 . 0
Change
( )
10
375 . 43
to binary.
Solution
Integer part
2 43
2 21 1
2 10 1
2 5 0
2 2 1
2 1 0
2 0 1

( ) ( )
2 10
101011 43
Decimal Part
0.375 x 2 = 0.75
0.75 x 2 = 1.50
0.50 x 2 = 1.00
Thus
( ) ( )
2 10
011 . 101011 0375 . 4
Questions
1) Convert the following numbers to the stated number system.
16
a)
( )
10
306 . 0
to duodecimal
b)
( )
10
731 . 492
to octal
c)
( )
10
426 . 384
to hexadecimal
d)
( )
10
65 . 0
to binary
Octal and Hexadecimal Conversions
Using the binary system as an intermediate stage, we can convert octal numbers to
hexadecimal numbers and vice versa.
Octal to Hexadecimal
1) Evaluate the binary equivalent of each octal number.
2) Regroup them into quadruplets and convert each group to its hexadecimal equivalent.
Hexadecimal to Octal
1) Evaluate the binary equivalent of each hexadecimal number.
2) Regroup them into triplets and convert to its octal equivalent.
Example
1) Convert
( )
8
243
to hexadecimal
Solution
2 2
2 1 0
2 0 1
2 0 0

( ) ( )
2 8
010 2
2 4
2 2 0
2 1 0
2 0 1
17

( ) ( )
2 8
100 4
2 3
2 1 1
2 0 1
2 0 0

( ) ( )
2 8
011 3
Thus
( ) ( )
2 8
010100011 243
Regrouping into 4s we have 0000 1010 0011
3 2 1 2 1 2 0 2 0 0011
10 2 0 2 1 2 0 2 1 1010
0 1 2 3
0 1 2 3
+ + +
+ + + A

( ) ( )
16 8
43 243
2) Convert
( )
16
8 . 39 B
to Octal
Solution
Converting each digit into binary gives
( ) ( )
( ) ( )
( ) ( )
( ) ( )
2 16
2 16
2 16
2 16
1000 8
1011
1001 9
0011 3

B
Regrouping into 3s
00 111 001.101 110 00

18
0 000
6 2 0 2 1 2 1 110
5 2 1 2 0 2 1 101
1 2 1 2 0 2 0 001
7 2 1 2 1 2 1 111
0 000
0 1 2
0 1 2
0 1 2
0 1 2

+ +
+ +
+ +
+ +

( ) ( )
16 16
56 . 71 8 . 39 B
Questions
1. Convert
a.
( )
10
654 . 348
b.
( )
10
371 . 428

c.
( )
10
245 . 163
to its octal, binary and hexadecimal forms
2. Express
a.
( )
16
6 1 . 2 4 A B
b.
( )
16
4 . 3 2 D E
to its binary, octal and denary forms.
REPRESENTING NUMBERS
Computers use binary digits to represent numbers and other information. The memory is
organized into strings of bits called words. Each string has the same length in a particular
computer, although different computers may use different word lengths. The largest
19
number a computer can store depends on its word length. For example the largest binary
number a 16bit word can hold is 16bits of 1. This binary number is equivalent to a
decimal value of 65535.

1 2 65535 2 1
16
15
0

i
i
The largest decimal number that can be stored in a computer is given by the relation

1 2
n
, where n is the word length in bits. Decimal numbers are first
converted into the binary equivalent and then represented in either fixed point form or
floating point form.
Fixed Point Form
For integers, the decimal or binary point is always fixed to the right of the least
significant digits, hence fractions are not included. Negative numbers are stored using the
2s complement.
Example.
Represent -13 in binary form
Solution

( ) ( )
2 10
01101 13
, the extra zero to the left of the binary number is to indicate that
the number is negative.
Note: If the left most digit is 1, the number is positive.
Converting the number into 1s complement.
Inverting each digit and adding 1 to the last bit we have
10010
+ 1
20
_____________
10011
( ) ( )
2 10
10011 13
The left most bit of a binary number which is used to indicate the sign is called the sign
bit. Thus we have n 0 bits to represent the number. Thus a 16 bit word can contain
numbers -2
15
to 2
15
-1 (-32768 to 32767).
Floating Point Representation
Large numbers and fractional numbers are stored and processed in exponential form.
These numbers have an embedded decimal point and are called floating point numbers or
real numbers. A floating point number is characterized by 4 parameters, the base , the
number of digits t and the exponent range (m, M).
Definition1
A floating point number is a number represented in the form

e
t
d d d ..... .
2 1
.(1)
Where
t
d d d ..... .
2 1
are integers and satisfy

i
d 0
.
The exponent e is such that M e m . The fractional part
t
d d d ..... .
2 1
is called the
Mantissa and it lies between +1 and -1.
The following numbers have been expressed in floating point form
1) 0 =
e
0 .... .......... 00 .
2)
2
10 357812 . 7812 . 35
3)
9
10 987654321 . 987654321
21
For floating point numbers the memory location is divided into 3 fields(part) as shown
below.
Typically, floating numbers use a field width of 32bits where 24 bits are used for the
mantissa, 7bits for the exponent.
Exercise
1) Convert the following numbers to floating numbers
a) 0.00596
b) 65.7451
c) -486.8
Normalization
The shifting of the decimal point to the left of the most significant digit is called
Normalization and the numbers represented in normalized form are called Normalized
Floating Point numbers.
Example: Given 0.00011101 x 10
7
, shifting the fractional part 3 places to the left results
in the number 0.11101 x 10
4
which is the normalized floating point number.




S

I

G

N
E X P O N E N T
M
A
N
T
I
S
S
A
22
Floating Point Arithmetic
Addition
If x + y = z, let the fractional parts and the exponents be f
x
, fy & fz and Ex, Ey and Ez,
then the addition algorithm is
i. Set Ez = the largest of Ex and Ey. Suppose Ex Ey, then Ez = Ex.
ii. Shift Fy to the right by Ex Ey places to make the exponent of Fx and Fy the
same.
iii. Set Fz = Fx + Fy.
iv. Normalize the sum and express as
z
E
z
f Z 10 .
Example
Add 0964572E2 and 0.586351E5.
Solution
5 587315 . 0
587315 . 0 586351 . 0 000964 . 0
000964 . 0
, 5
2 964572 . 0
5 586351 . 0
E Z
f
f
E
E y
E x
z
y
z

Question
Add 0.735816E4 and 0.635742E4
Subtraction
Subtract 0.994576E-3 from 0.999658E-3
23
Solution
5 5082 . 0
2 5082 . 0 005082 . 0 0994576 999658 . 0
3
3 994576 . 0
3 999658 . 0





E Z
E f
E
E y
E x
z
z
Multiplication
Algorithm
i. Multiply the fractional part: y x z
f f f
ii. Add the exponents: y x z
E E E +
iii. Normalize if necessary.
Example
Multiply out 0.200000E4 and 0.400000E-2
Solution
1 800000 . 0 2 0800000 . 0
2 2 4
080000 . 0 400000 . 0 200000 . 0
E E Z
E
f
z
z



Division
Algorithm
iv. Divide the fractional part: y x z
f f f
v. Subtract the exponents: y x z
E E E
vi. Normalize if necessary.
24
Example
Divide 0.876543E-5 by 0.200000E-3
Solution

1 4382715 . 2 382715 . 4
2 3 5
382715 . 4 200000 . 0 876543 . 0



E E Z
E
f
z
z
Exercise
1. Add 0.500000E1 and 0.100000E-7
2. Multiply 0.350000E40 by 0.500000E70
3. Divide 0.875000E-18 by 0.200000E95
4. Subtract 0.499998 from 0.500000
5. let
248000 . 0
243451 . 0
10 456732 . 0
2

z
y
x
, show that
a. (x + y) + z = x + (y + z)
b.
( ) ( ) z y x z y x
c.
( ) ( ) ( ) z x y x z y x
Definition2
A non-zero floating point number (1) is in normal form if the value of the mantissa lies in
the interval
1
]
1

1
, 1
or in the interval
1
]
1

1 ,
1
.

.
25
Definition3
A non-zero floating point number (1) is in t-digit mantissa standard from if it is
normalized and its mantissa consists of exactly t digits.
Is a number x has the representation in the form

e
t t
d d d d x
+
......... ..... .......... .......... .......... .......... .
1 2 1
.(2)
Then the floating point number f(x) in t-digit mantissa standard form can be obtained in
the following ways.
1. Chopping
Here we neglect
.. .......... .......... ,
2 1 + + t t
d d
in (2) and obtain
( )
e
t
d d d x f ..... .......... .......... .......... .......... .
2 1

(3)
2. Rounding
Here the fractional part in (2) is written as

e
t
d d d +1 ..... .......... .......... .......... .......... .
2 1
if
5
1

+ t
d
and the first
digits are taken to write the floating point number.
Example
Find the sum of 0.123x10
3
and 0.456x10
2
and write the results in 3digit mantissa.
Solution
3
3
3
10 1686 . 0
10 0456 . 0
10 123 . 0



z
y
x
f
f
f

26
= 0.168 x 10
3
for Chopping
= 0.169 x 10
3
for rounding.
Week 3
APPROXIMATION AND ERRORS.
A computer has a finite word length and so only a fixed number of digits are stored and
used during computation. This means during storing exact decimal numbers in its
converted form in the computer memory, an error is introduced. This error is machine
dependent and is called machine epsilon. After the computation is over, the result in the
machine form (with base ) is again converted to decimal form understandable to the
users and some more error may be introduced at this stage.
The error = True value Approximate value
The relative error =
trueValue
Error
(5)
Absolute error =
Error
(6)
27
Types of Errors
1) Inherent Error
these are errors present in the data supplied to the computer. They are present in the
statement of the problem before solution. They are of two types.
a) Data Errors
These arise when data is obtained by some experimental means and are therefore
of limited accuracy and precision.
b) Conversion Errors
These arise due to the limitation of the computer to store the data exactly after
converting from one number system to another.
2) Numerical Errors
They are introduced during the process of implementation of a numerical method.
They are of two forms;
a) Round-off Errors
They occur when a fixed number of digits are used to represent exact numbers.
The round off error is the quantity e which must be added to the finite
representation of a computed number in order to make it the true representation of
that digit. Thus, if x is the computed number given by

e
t t
d d d d x
+
......... ..... .......... .......... .......... .......... .
1 2 1
,
then thye relative error (5) for t-digit mantissa standard form representation of x
becomes
28

( )
rounding
g forchoppin
x
x f x
t
t

1
1
2
1

Thus the bound on the relative error of a floating point number is reduced by half
when rounding is used than chopping.
b) Chopping Errors
The extra digits are dropped. For instance if we use a computer with a fixed word
length of 4 digits, then the number 42.79893 can be expressed as follows

( )
( )
2 4
2
2
10 10 93 . 0 4278 . 0
10 0000093 . 4278 . 0
10 427893 . 0
+
+

x
This can be expressed in the general form as
True x =
( )
Error ion Approximat
g f
g f
d E
x
E
x
E d
x x
+
+
+

10 10
10 10
Where f
x
- Mantissa, d - length of the mantissa, E exponent.
SOLUTION OF NON-LINEAR EQUATIONS
Consider equations of the form
( ) 0 x f
.. 2.1
29
Where
( ) ( )
n n
n n
n
a x a x a x x p x f + + + +

1
1
1
...... ..........
is a polynomial of degree
in x.
Definition
A number is a solution of f(x) = 0, if f( ) . Such a solution is called a root or zero
of f(x) = 0.
Geometrically, a root of the equation 2.1 is the value of x at which the graph of y = f(x)
intersects the x axis. Equation 2.1 can be solved using the following two methods.
i. Direct Methods
These methods give the exact value of the roots in a finite number of steps.
ii. Iterative methods
These methods are based on the idea of successive approximation, that is starting
with one or more initial approximations to the root, we obtain a sequence of
approximations or iterates (x
k
) which in the limit converges to the root.
Definition
A sequence of iterates (x
k
) is said to converge to the root
( )
if

0 lim

k
k
x
If x
k
, x
k-1
., x
k-m+1
are m approximations to the root then a multipoint iteration method is
defined as

( )
1 1 1
,......, ,
+ +

m k k k k
x x x x
.
The function is called the multipoint iteration function. To get an appropriate initial
approximation it might be necessary to sketch the curve so that any value in the
30
neighbourhood of the point the curve crosses the x axis may be taken as an initial
approximation.
Alternatively, we can use the Intermediate Value theorem stated below.
Theorem
If f(x) is a continuous function on some initial interval
[ ] b a,
and f(a)f(b) < 0 then the
equation f(x) = 0 has atleast one real root or an odd number of roots in the interval (a,b).
Example
Obtain an initial approximation to a root of the equation f(x) = cosx xe
x
= 0
Solution
We prepare a table of the values of the function f(x) for various values of x.
x 1 0.5 1 1.5 2
f(x) 1 0.0532 -2.1780 -6.6518 -15.1942
From the table f(x) = 0, has at least one root in the interval (0.5, 1).
The exact root correct to 10d.p is 0.5177573637.
Bisection Method
This method is based on the repeated application of the intermediate value theorem.
Suppose the root f(x) = 0 lies in the interval I
0
= (a
0
, b
0
), then we determine
2
0 0
1
b a
m
+

and denote by I
1
, the new subinterval which satisfies the IVT.
31
We then bisect I
1
and get a subinterval I
2
which satisfies the IVT. Continuing this way we
obtain a sequence of nested sets of such intervals
.....
2 1 0
I I I
such that each
subinterval contains the root.
Suppose we repeat the bisection q times, then we obtain either the root or the subinterval
I
q
of length
q
a b
2
0 0

which contains the root.
We take the midpoint of the last subinterval as the desired approximation to the root. If
the permissible error is , then the approximate number of iterations required is obtained
from the relation

( )
2 log
log log
2
0 0 0 0

a b
n
a b
n
Example
Perform five iterations of the bisection method to obtain the smallest positive root of the
equation f(x) = x
3
5x + 1 = 0
Solution
Since f(0) = 1 > 0 and f(1) = -3 < 0, then the smallest root lies in the interval (0, 1).
Taking a
0
= 0 and b
0
= 1 we get,

( ) ( ) 5 . 0 1 0
2
1
2
1
0 0 1
+ + b a m
F(m1) = -1.375 and f(a
0
)f(m
1
)<0.
Thus the root lies in the interval (0, 0.5). The sequence of interval are given in the table
below.
k a
k-1
b
k-1
m
k
f(m
k
)
32
1 0 1 0.5 < 0
2 0 0.5 0.25 < 0
3 0 0.25 0.125 < 0
4 0.125 0.25 0.1875 < 0
5 0.1875 0.25 0.21875 < 0
Hence the root lies in (0.1875, 0.21875)
x = 0.203125
ITERATIVE METHODS BASED ON 1
ST
DEGREE EQUATIONS
Suppose f(x) = a
0
x + a
1
= 0 .2.1,
is a 1
st
degree approximation of f(x) then the solution of 2.1 is given by

0
1
a
a
x

3.1
Where a
0
= 0 and a
1
are arbitrary parameters.
SECANT METHOD
If x
k-1
and x
k
are two approximations to the root, then to get a0 and a1 we use the
conditions
1 1 0 1
a x a f
k k
+
, where
( )
1 1

k k
x f f

1 0
a x a f
k k
+
, where
( )
k k
x f f
33
( ) ( )
( ) ( )

1
1 1
1
1
1
0
k k
k k k k
k k
k k
x x
fx x f x
a
x x
x f x f
a
..4.1
Which implies
( ) ( )
( ) ( )
1
1 1
1

k k
k k k k
k
x f x f
x f x x f x
x
..5.1
This is called the Secant or the Chord Method.
34
THE REGULA FALSI METHOD
If the approximations in the secant method are such that f(x) f(x
k-1
) < 0, then the method
is known as the Regula-Falsi method.
Example
Use the Secant and Regula-Falsi methods to determine the root of the equation
Cos x xe
x
= 0
Solution
Taking the initial approximations as x
0
= 0, x
1
= 1, we have for the secant method
F(0) = 1
F(1) = cos 1 e = -2.17797523
( ) ( )
( ) ( )
( ) ( )
3146653378 . 0
1 177979523 . 2
1 1 177979523 . 2 0
0 1
0 1 1 0
2

x f x f
x f x x f x
x
F(x
2
) = f(0.3146653378) = 0.519871175
( ) ( )
( ) ( )
446728144 . 0
1 2
1 2 2 1
3

x f x f
x f x x f x
x
The computed results are as follows.
k x
k+1
f(x
k+1
)
2 0.44678144 0.519871
3 0.5317058606 -0.429311 x 10
-1
4 0.5169044676 0.259276 x 10
-2
5 0.5977477653 0.301119 x 10
-4
6 0.5177573708 -0.215132 x 10
-7
7 0.5177573637 0.178663 x 10
-12
35
8 0.517757367 0.222045 x 10
-15
Hence the root is 0.5178 (4d.p)
The table for Regula- Falsi method is
k x
k+1
f(x
k+1
)
1 0.3146653378 0.519871
2 0.4467281446 0.203545
3 0.4940153366 0.708023 x 10
-1
4 0.5099461404 0.236077 x 10
-1
.
.
.
.
10 0.5177478783 0.288554 x 10
-4
.
.
20 0.5177573636 0.396288 x 10
-9
x = 0.5178 (4d.p)
Note: The Secant methods converges faster than the Regula-Falsi method.
THE NEWTON-RAPHSON METHOD
Suppose f(x
k
) = a
0
x
k
+ a1, then f`(x
k
) = a
0
.6.1
a
1
= - x
k
f`(x
k
) - f(x
k
)
From 3.1, we have
36

( )
( )
k
k
k k
x f
x f
x x
'
1

+
which is the Newton-Raphson Method.
Example
Apply Newton-Raphson Method to determine a root of the equation
f(x) = Cos x xe
x
= 0 such that f(x*) < 10
-8
where x* is the approximation to the root.
Solution
f(x) = Cos x xe
x
= 0
( )
x x
e xe x x f sin
'
k k
k
k k
k
x x
k k
k
x
k
k k
x x
k k
x
k k
k k
e e x x
x e x x x
e e x x
e x x
x x
+ +
+ +

+
sin
cos sin
sin
cos
2
1
Since the roots lie in
[ ] 1 , 0
we set x
o
= 1 and obtain the table below.
k x
k
f(x
k
)
0 1
1 0.653079406 -4.606 x 10
-1
2 0.531343367 -4.180 x 10
-2
3 0.517909913 -4.641 x 10
-4
4 0.51775738 -5.926 x 10
-7
5 0.517757363 -2.910 x 10
-10
X 0.5178

37
POLYNOMIAL INTERPOLATION
Suppose that we have a table of numerical values of a function
x x
0
x
1
x
n
y y
0
y
1
y
n
Table 1.1
We are faced with three problems
i. To find a simple and convenient formulas that reproduces the given points
exactly.
ii. We assume, given the table of numerical values it is contaminated by errors. We
therefore seek a formula that represents the data(approximately) and if possible
filter out the errors.
iii. We need to find a function f that is simple to evaluate and produce a reasonable
approximation to g(which might be given) with full machine precision.
In all these problems, a simple function p can be obtained that represents or approximates
the given table / function f. the representation p can always be taken to be a polynomial.
Uses of Polynomials
i. Reconstruct the function f(x) when it is not given explicitly and only the values of
f(x) and / or its certain order derivatives at a set of points called nodes, tabular
points or arguments are known.
ii. To represent the function f(x) by the interpolating polynomial p(x) so that
common operations such as determination of roots, differentiations and
integrations may be performed using p(x).
38
Definition
A polynomial p(x) is called interpolating polynomial if the values of p(x) and / or its
certain order derivatives coincide with those of f(x) and /or its same order derivatives at
one or more tabular points. Its represented as

( )
n
n n
x a x a x a a x P + + + + ... ..........
2
2 1 0
,
where n is a non negative integer and a
0
, a
1
,.. a
n
are constants.
TAYLORS INTERPOLATION
If the polynomial p(x) is written as the Taylors expansion for the function f(x) at a point
[ ] b a x x , ,
0 0

in the form

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
0 0 1
'
' 2
0 1
'
0 0
!
1
.....
! 2
1
x f x x
n
x f x x x f x x x f x p
n n
+ + + +

4.1
Then p(x) may be regarded as an interpolating polynomial of degree n, satisfying the
condition.

( )
( )
( )
( )
0 0
x f x p
x k
, k = 0, 1,.., n. 4.2
The term
( )
( )
( )
( )
1 1
0
! 1
1
+ +

n n
n
f x x
n
R
, x0 < < x
4.3
Which has been neglected in 4.1 is called the remainder or the truncation error.
39
The number of terms to be included in 4.1 may be determined by the acceptable error. If
this error > 0 and the series in truncated at the term f
(n)
(x
0
), then

( )
( )( )
( )

+

+
+
+
+
+
1
1
0
1
1
0
! 1
1
! 1
1
n
n
n
n
M x x
n
or
f x x
n
4.4
Where
( )
( ) x f M
n
b x a
n Max
1
1
+

+

Example1
Obtain a polynomial approximation p(x) to f(x) = e
-x
using the Taylors expansion about
x
0
= 0 and determine
i. X when the error in p(x) obtained from the 1
st
four terms only is to be less than 10
-
6
after rounding.
ii. They number of terms in the approximation to find results correct to 10
-10
for
1 0 x .
Solution
i. From f(x) = e
-x
, we have

( ) ( )
( ) ( )
( ) ( )
( ) ( ) ........ 1 , 0 , 1 0
1
.
.
1
1
1
1 ' '
1 '

r f
and
e x f
e x f
e x f
r r
r r
from 4.1, ( )
6 2
1
3 2
x x
x x p +
and from 4.4,
40
7
4
4
6
4
4
10 5 24
10 .
2
1
! 4
1

<
M x
M x
where
( )
( ) 1 max max
1 0
4
1 0
4



x
x x
e x f M
x = 120 x 10
-7
< 0.058856619
x < 0.06
ii. From 4.1 we obtain

( )
11
4
4
10 .
2
1
! 1
1

+
M x
n

( )
11
10 5
! 1
1

<
+ n
, x = 1, M
4
= 1
n 14
LINEAR INTERPOLATION
From Table 1.1, we assume that the x
i
s form a set of n +1 distinct points. The table
represents n+1 points in the Cartesian plane and we want to find a polynomial curve that
passes through all the points. Thus we seek to determine a polynomial that is defined for
all x and takes on the corresponding values of y
i
for each of the n+1 distinct x
i
s in this
table. A polynomial p for which p(xi) = y
i
when n i 0 is said to interpolate the table.
The points x
i
are called nodes.
Consider the 1
st
and simple case, n = 0. Here a constant function solves the problem i.e
the polynomial p of degree 0 defined by p(x) = y
0
reproduces the one none table.
41
For n = 1, since a straight line can be passes through two pints, a linear function is
capable of solving the problem. Explicitly, the polynomial is defined by

( )
1
0 1
0
0
1 0
1
y
x x
x x
y
x x
x x
x P

,
_

,
_

( )
0
0 1
0 1
0
x x
x x
y y
y

,
_

+
..4.5
is of 1
st
degree and reproduces the table. In this case p(x
0
) = y
0
and p(x
1
) = y
1
.
This p is used for linear interpolation.
Example 1
Find the polynomial of least degree that interpolates the table below.
x 1.4 1.25
y 3.7 3.9
Solution
By definition

( )
1
0 1
0
0
1 0
1
y
x x
x x
y
x x
x x
x P

,
_

,
_

( ) 4 . 1
3
4
7 . 3
9 . 3
4 . 1 25 . 1
4 . 1
7 . 3
25 . 1 4 . 1
25 . 1

,
_

+
,
_

x
x x
42
Example 2
Find a polynomial of degree 2 or less to approximate f(x) = sin x near x
0
= 0 and use this
polynomial to approximate sin(0.1).
Solution
The equation of this approximating polynomial is

( )
3
3
2
2 1 0 3
x a x a x a a x P + + +
To determine the constants, we let

( ) ( ), 0 0 f P

( ) ( ), 0 0
' '
f P

( ) ( ), 0 0 ' '
' '
f P

( ) ( ), 0 0
' ' ' ' ' '
f P
x
0
= 0
P(0) = a
o
, f(0) = sin 0 = 0 a
o
= 0
( )
( )
1
'
2
3 2 1
'
0
3 2
a P
x a x a a x P

+ +
and
( )
( ) 1 0 cos 0
cos
'
'

f
x x f
a
1
= 1
( )
( )
2
' '
3 2
' '
2 0
6 2
a P
x a a x P

+
and
( )
( ) 0 0 sin 0
sin
' '
' '


f
x x f
a
2
= 0
( )
( )
3
' ' '
3
' ' '
6 0
6
a P
a x P

and
( )
( ) 1 0 cos 0
cos
' ' '
' ' '


f
x x f

6
1
3
a
The approximating polynomial of degree 3 is given by
( )
6
3
x
x x P
( ) ( )
( )
6
1 . 0
1 . 0 1 . 0 1 . 0 sin
3
P
43
0.099833
44
LAGRANGES INTERPOLATION
Suppose we wish to interpolate arbitrary functions at a set of nodes x
0
, x
1
, x
n
. We
first define a system of n+1 special polynomial of degree n known as cardinal
polynomials. These are denoted by l
o
, l
1
,l
n


( )
1 0
1
0
x x
x x
x l

and
( )
0 1
0
1
x x
x x
x l

at x = x
0
, L
0
(x
0
) = 1, L
1
(x
0
) = 0
x = x
1
, L
0
(x
1
) = 0, L
1
(x
1
) = 1
Once these are available, we can interpolate any function f by the Lagrange form of the
interpolating polynomial

( ) ( ) ( ) ( ) ( ) ( ) ( )
n n n
x f x L x f x L x f x L x P + + + ........ ..........
1 1 0 0


( ) ( )
i
n
i
i
x f x l

0
where
( )
j i
j
n
i j
j
i
x x
x x
x l

0
The formula indicates that l
i
(x) is the product of n linear factors
( )

,
_

,
_

,
_

,
_

,
_

+
+

n i
n
i i
i
i i
i
i i
i
x x
x x
x x
x x
x x
x x
x x
x x
x x
x x
x l . .......... .......... ..........
1
1
0
1
1
1
0
0
Example
Determine the 2
nd
degree interpolating polynomial for
( )
x
x f
1

using the nodes x

0
=2,
x
1
=2.5, and x
2
=4.0.
Solution
45

( ) ( ) ( ) x l x f x P
i
i
i

2
0
2

( ) ( ) ( ) ( ) ( ) ( ) x l x f x l x f x l x f
2 2 1 1 0 0
+ +

(1)
( ) 5 . 0
2
1
0
x f
,
( ) 4 . 0
5 . 2
1
1
x f
,
( ) 25 . 0
0 . 4
1
2
x f

and the coefficients are given by
( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
10 5 . 6
4 2 5 . 2 2
4 5 . 2
2
2 0 1 0
2 0
0
+

x x
x x
x x x x
x x x x
x l
( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
667 . 10 6 33 . 1
4 5 . 2 2 5 . 2
4 2
2
2 1 0 1
1 0
1
+

x x
x x
x x x x
x x x x
x l
( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
667 . 1 5 . 1 33 . 0
5 . 2 4 2 4
5 . 2 2
2
1 2 0 2
1 0
2
+

x x
x x
x x x x
x x x x
x l
Substituting in the polynomial (1), we have
( ) ( ) ( ) ( ) 667 . 1 5 . 1 333 . 0 25 . 0 667 . 10 6 33 . 1 4 . 0 10 5 . 6 5 . 0
2 2 2
2
+ + + + x x x x P
= 0.05003x
2
0.425185x + 1.15025
P
2
(x) 0.05x
2
0.425x + 1.15
46
Example 2
Find the Lagranges interpolating polynomial to interpolate the table below.
x
3
1
4
1 1
f(x) 2 -1 7
Solution
( )
( )
( ) 1
4
1
18
1
3
1
4
1
3
1
1
4
1
0

,
_

,
_

,
_

,
_

x x
x x
x l
( )
( )
( )
( ) 1
3
1
16
1 4
3
1
4
1
1
3
1
1

,
_

,
_

,
_

x x
x x
x l
( )
,
_

,
_

,
_

,
_

,
_

,
_

4
1
3
1
2
4
1
1
3
1
1
4
1
3
1
2
x x
x x
x l
( ) ( ) ( )
1
]
1

,
_

,
_

+
1
]
1

,
_

1
]
1

,
_

4
1
3
1
2 7 1
3
1
16 1 1
4
1
18 2
2
x x x x x x x P

( ) ( )
,
_

,
_

+
,
_

,
_

4
1
3
1
14 1
3
1
16 1
4
1
36 x x x x x x

2
38
6
349
6
79
x x +
47
NEWTONS DIVIDED DIFFERENCE INTERPOLATION
This is in the form

( ) ( )
( ) ( )
( ) ( ) [ ]( )
0 1 0 0 0
0 1
0 1
0
, x x x x f x f x x
x x
x f x f
x f x P +

+
.4.6
Where
( ) ( )
[ ]
1 0
0 1
0 1
, x x f
x x
x f x f

and is called the 1

st
divided difference of f(x)
relative to x
0
and x
1
.
Equation 4.6 may be written as

( ) ( )
[ ]
1 0
0
0
, x x f
x x
x f x P

.4.7
Equation 4.6 and 4.7 are the linear Newtonian interpolating polynomial with divided
differences.
TRUNCATED ERROR BOUNDS
The polynomial p(x) coincides with the function f(x) at x
0
and x
1
and it deviates at all
other points in the interval (x
0
, x
1
) as shown below.
48
49
This deviation is called the truncation error and may be written as
E(f,x) = f(x) p(x).
Rolles Theorem
If g(x) is continuous on the interval [a,b] and if g(a) = 0, g(b) = 0, then there is at least
one point inside (a,b) for which g`( ) = 0.
If
[ ] b a x ,
, 0
x x
, x1 is fixed, then for this x we define a function g(t) as

( ) ( ) ( ) ( ) ( ) [ ]
( ) ( )
( ) ( )
1 0
1 0
x x x x
x t x t
x P x f t P t f t g



..4.8
g(t) = 0 for t = x
0
, x
1
and x.
Differentiating 4.8 twice with respect to x we get
50

( ) ( ) ( ) ( ) ( )
( )
( ) ( )
1
]
1

1 0
1 0 ' ' '
2
x x x x
x x t
x P x f t P t f t g

( ) ( )
( ) ( ) [ ]
( ) ( )
1 0
' ' ' '
2
x x x x
x P x f
t f t g

, since P

(t) = 0 by Rolles Theorem. ..4.9

Solving 4.9 we have

( ) ( )( ) ( )
' '
1 0
2
1
) ( f x x x x x P x f +
4.10
Where min(x
0
, x
1
, x) < < max (x
0
, x
1
, x)
the truncation error in linear interpolation is given by

( ) ( )( ) ( )
' '
1 0 1
2
1
; f x x x x x f E
4.11
The bound for f

(x) in [x
0
,x
1
] i.e
( ) [ ]
1 0 2
' '
, , x x x m x f
, then
( ) ( ) ( ) ( ) ( )
' '
1 0
2
1
f x x x x x P x f
( )( ) ( )
( )( )
2 1 0
' '
1 0
1 0
1 0
max
2
1
max
2
1
M x x x x
f x x x x
x x x
x x x

..4.12
The max value of
( ) ( )
1 0
x x x x
occurs at x =
( )
1 0
2
1
x x +
and 4.12 becomes

( ) ( ) ( ) ( )
2 1 0 0 1
2
1
2
1
2
1
M x x x x x P x f

( )
2
2
0 1
8
1
M x x
.4.13
51
For fully spaced nodal points x
i
= a + ih, i = 0, 1, n and
n
a b
h

, the max
truncation error using the linear interpolating polynomial P(x) is less than a given > 0,
we have
( ) ( ) ( )

x f
h
x P x f
b x a
' '
2
max
8
.4.14
Example1
Using sin(0.1) = 0.09983 and sin(0.2) = 0.19867, find an approximate value of sin (0.15)
by Lagranges interpolation, obtain a bound on the truncation error.
Solution
( )
( ) ( ) ( ) 19867 . 0
1 . 0 2 . 0
1 . 0 15 . 0
09983 . 0
2 . 0 1 . 0
2 . 0 15 . 0
15 . 0
1
1
0 1
0
0
1 0
1
1

P
f
x x
x x
f
x x
x x
x P
= 0.049915 + 0.099335
= 0.14925
The truncation error is

( ) ( )( ) ( )
' '
1 0 1
2
1
, f x x x x x f E
=
( )( )( ) sin 2 . 0 1 . 0
2
1
x x
Where
2 . 0 1 . 0
, ( ) sin
' '
f
The maximum value of
[ ] 2 . 0 , 1 . 0 , sin
is sin 0.2 = 0.19867,
52
Thus
( )
( )( )
( ) 19867 . 0
2
2 . 0 15 . 0 1 . 0 15 . 0
;
1

x f E
= (0.00125)(0.19867)
0.00025
Example2
Determine the stepsize h to be used in the tabulation of f(x) = sin x in the interval [1,3] so
that the linear interpolation will be correct to 4 decimal places.
Solution
( )
4 ' '
3 1
2
10
2
1
8
max


x f
h
x
and f(x) = sin x, f

(x) = cos x, f

(x) = -sin x

1 sin max
3 1


x
x

5
2
10 5 1 .
8


h
,

02 . 0 h
53
WEEK 7 and 8
1) Least square approximation to find an approximation to a function f(x) given in
tabular form.
2) Evaluate errors of interpolating polynomials.
3) Use divided differences to determine the explicit representation of an interpolating
polynomial.
APPROXIMATION
The existence of a polynomial function P(x) which approximates any continous function
f(x) on a finite interval
[ ] b a,
is guaranteed by the Weierstrass approximation Theorem.
Weierstrass approximation Theorem
If the function f(x) is continuous on a finite interval
[ ] b a,
, then given any > 0, there
exists a n = n() and a polynomial P(x) of degree n such that

( ) ( ) [ ] b a x x P x f , <
In order to determine an approximation to f(x) we assume an expression of the form

( ) ( )
n
C C C x P x f ........ .......... , ,
1 0

( ) ( ) ( ) x C x C x C
n n
+ + + .. ..........
1 1 0 0
(1)
Where
( ) x
i

(i = 0, 1, , n) are independent functions and the parameter

c
i
(i = 0, 1, , n) are constants to be determined.
The function
( ) x
i

are called Coordinate Functions which for polynomial

approximations are considered as
( )
i
i
x x
, (i = 0, 1, , n)
The error of the approximation is defined as

( ) ( ) ( ) ( ) ( ) c C c C c C x f E
n n
+ + + .......
1 1 0 0
.(2)
54
Where
.
is a well defined norm. the aim of approximation is to determine the
coefficient c
i
(i = 0, 1, , n) inorder that the error is made as small as
possible.
For different types of norm, we obtain different types of approximations. Once a
particular norm is fixed the function which make these error smallest according to this
norm is called the Best Approximation.
The most commonly used norms are;
Norm For Discrete Data
a) Lp Norm is defined as
( )

n
i
p
p
i
x x
1
1
P 1 .(3)
b) Euclidean Norm

2
1
1
2

,
_

n
i
i
x x
.(4)
written as
2
x
and is called the square norm.
c) Uniform Norm
j
n i
x Max x

1
(5)
Which is a particular case of (3) for P .
Norm for Continuous Data
55
If the function f(x) is continuous in the interval
[ ] b a,
, then the norm is
a)
( ) ( )
p
b
a
P P
dx x f x w f Norm L
1

'

, P 1 .(6)
Where4 w(x) > 0 and is the weighted function.
b) For p = 2, we have the Euclidean or square norm

( ) ( )
2
1
2
2

'

b
a
dx x f x w f
.(7)
c) For p = , we have the uniform norm.

( ) x f Max f
b i a

.(8)
When we use the Euclidean norm we obtain the Least Square Approximation and when
uniform norm is used we get the Uniform Approximation.
Least Square Approximation
Least Square Approximations are most commonly used approximations for
approximating a function f(x) which may be given in tabular form or known explicitly
over a given interval. In this case we use the Euclidean norm (4). The best approximation
in the least square sense is defined as that for which the constants C
i
(i = 0, 1.., n )
are determined so that the aggregate of the weighted function w(x) over a given interval
is as small as possible for w(x) > 0.
56
For functions whose values are given at n + 1 points x
0
, x
1
, ..x
n
, we have
( ) ( ) ( ) ( ) Min x C x f x w C C C I
n
k
n
i
k i i i k n

1
]
1

0
2
0
1 0
,...., , ..(9)
For functions which are continuous over the interval
[ ] b a,
( ) ( ) ( ) ( ) Min dx x C x f x w C C C I
n
n
i
i i
b
a
n

1
]
1

2
0
1 0
, , ..(10)
Where the coordinate
( )
i
i
x x
, i = 0, 1, ., n. and the weight function w(x) = 1.
The necessary condition for equation (9) and (10) to have a minimum value is that

0

i
C
I
, i = 0, 1, ., n
This gives a system of n + 1 linear equations in n + 1 unknowns C
0
, C
1
.C
n.
These equations are called the Normal equations.
The normal equations for (9) and (10) are respectively
( ) ( ) ( ) ( ) 0
0 0

1
]
1

k j
n
i
k i i k
n
k
x x C x f x W
(12)
and
( ) ( ) ( ) ( ) 0
0

1
]
1

dx x x C x f x W
j
n
i
i i

, j = 0, 1, 2.n .........(13)
57
Example
Obtain a linear polynomial approximation to the function f(x) = x
3
on interval
[ ] 1 , 0

using the least square approximation with W(x) = 1.
Solution
This equation is continuous hence we use a linear polynomial
P(x) = C
0
+ C
1
(x) , where C
0
and C
1
are arbitrary constants.
Using equation (10)

( ) ( ) [ ] Min dx x C C x C C I +

2
1 0
3
1
0
1 0
1 ,

( ) ( )
) 1 .( .......... .......... .......... ..........
3
1
5
2
2
1
7
1
2 2 2
2
2
1 1 0
2
0 1 0
2 2
1
1
0
1 0
2
0
4
1 0
3 6
1
0
2
1 0 1 0
3 6
C C C C C C
dx x C x C C C x C C x x
dx x C C x C C x x
+ + + +
+ + +
+ + +

The necessary and sufficient conditions for a minimum to occur is given by equation (11)
0

i
C
I
Taking the partial derivatives of equation (1) above we have
58
0
3
2
5
2
0 2
2
1
1 0
1
1 0
0
+ +

+ +

C C
C
I
C C
C
I
.(2)
Equation (2) is known as the Normal equations.
Solving the normal equations simultaneously, we get
5
1
0
C
and
10
9
1
C
The polynomial will be
( )
10
2 9

x
x P
Example 2
Obtain the least square polynomial approximation of degree 1 and 2 for f(x) = x on the
interval
[ ] 1 , 0
.
Solution
W(x) = 1.
a) For n = 1
( ) ( ) Min dx x C C x C C I
1
]
1

2
1 0
2
1 1
0
1 0
1 , (1)
The necessary and sufficient conditions for a minimum
0

i
C
I
0
2
1
3
2
2
1 0
0

,
_

C C
C
I

0 2
3
4
1 0
+ + C C
59

4 3 6
1 0
+ C C
.(a)
0
3
1
2
1
5
2
2
1 0
1

,
_

C C
C
I

0
3
2
5
4
1 0
+ + C C

12 10 15
1 0
+ C C
.(b)
Solving Simultaneously (a) and (b) we have

15
4
0
C
and
5
4
1
C

( )
15
12 4
5
4
15
4 x
x x P
+
+
b) For n = 2
( ) ( ) Min dx x C x C C x C C C I
1
]
1

+ +

2
2
2 1 0
2
1 1
0
2 1 0
1 , , .(2)
The least square polynomial is of the form
( )
2
2 1 0
x C x C C x P + +
0
3
1
2
1
3
2
2
2 1 0
0

,
_

C C C
C
I

0
3
2
2
3
4
2 1 0
+ + + C C C
(a)
60
0
4
1
3
1
2
1
5
2
2
2 1 0
1

,
_

C C C
C
I

0
2
1
3
2
5
4
2 1 0
+ + + C C C
.(b)
0
5
1
4
1
3
1
7
2
2
2 1 0
1

,
_

C C C
C
I

0
5
2
2
1
3
2
7
4
2 1 0
+ + + C C C
(c)
Rearranging (a), (b) and (c), we have

120 84 105 140
24 15 20 30
4 2 3 6
2 1 0
2 1 0
2 1 0
+ +
+ +
+ +
C C C
C C C
C C C
Solving the above equations simultaneously, we have

35
48
1
C
,
7
4
2
C
and
35
6
2
C

( )
2
7
4
35
48
35
6
x x x P +
TCHEBYSHEV POLYNOMIALS
61
The Tchebyshev polynomial of the 1
st
kind T
n
(x) is defined on the interval
[ ] 1 , 1
are
given by
( ) ( ) ( ) n x n x T
n
cos cos cos
1


.(1)
and satisfies the differential equations
( ) 0 1
2 ' ' ' 2
+ y n xy y x (2)
One independent solution of (2) gives the Tn(x) and the second independent solution
gives Chebyshevs polynomial of the 2
nd
kind U
n
(x).
( ) ( ) [ ] x n x U
n
1
cos 1 sin

+ (3)
The Tchebyshev polynomial T
n
(x) satisfies the recurrence relation

( ) ( ) x T x xT T
n n n 1 1
2
+

..(4)
From equation (4)
( ) ( ) 1 0 cos cos 0 cos
1
0


x x T
Thus we have

( )
( )
( )
( )
( ) 1 8 8
3 4
1 2
1
2 4
4
3
3
2
2
1
0
+

x x x T
x x x T
x x T
x x T
x T

62
Thus
( )
( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( ) ( ) x T x T x T x
x T x T x
x T x T x
x T x
x T
0 2 4
3
4
1 3
2
3
0 2
2
1
0
3 4
2
1
3
2
1
2
1
1
+ +
+
+

Properties of Tchebyshev polynomial

1. T
n
(x) is a polynomial of degree n and if n is even T
n
(x) is an even polynomial and if n
is odd T
n
(x) is odd polynomial.
2. T
n
(x) has n simple zeros
n k
n
k
x
k
,...., 2 , 1 ,
2
1 2
cos
,
_

, on the interval
[ ] 1 , 1
.
3. T
n
(x) assumes extreme values at n + 1 points
n k
n
k
x
k
,...., 2 , 1 , cos
,
_

and the
extreme value at x
k
is (-1)
k
.
4.
( ) [ ] 1 , 1 , 1 x x T
n
5. If P
n
(x) is any polynomial of degree n with leading coefficient unity (monomial) and
( ) ( ) x T x T
n
n
n
1
~
`
2
1

is the monic Chebyshev polynomial.

6. T
n
(x) are orthogonal with respect to the weight function

( )
2
1
1
x
x W

63

( ) ( )
0 ,
0 ,
2
, 0
1
1
1
2

n m
n m
n m
dx
x
x T x T
n m

Example
Using the Chebyshev polynomial, obtain the least squares approximation of second
degree for ( )
4
x x f on
[ ] 1 , 1
.
Solution

( ) ( ) ( ) ( ) x T C x T C x T C x f
2 2 1 1 0 0
+ +
.
We have
( ) ( ) [ ] min
1
1
, ,
2
2 2 1 1 0 0
4
1
1
2
2 1 0
+ +

dx T C T C T C x
x
C C C I
( ) [ ]
( ) [ ]
( ) [ ]
2
1
1
2
0
1
2
8
3
1
1
0
1
2
0
1
2
0
1
2
2
2
4
2
2
1
4
1
2
0
4
0
2
0
2 2 1 1 0 0
4
1
1 2
2
0
2 2 1 1 0 0
4
1
1 1
2
0
2 2 1 1 0 0
4
1
1 0

+ +

+ +

+ +

dx
x
T x
C
dx
x
T x
C
dx
x
T x
C
x
dx T
T C T C T C x
C
I
x
dx T
T C T C T C x
C
I
x
dx T
T C T C T C x
C
I

64
The required approximation is

( )
2 0
2
1
8
3
T T x f +
65
WEEK 9 and 10
1) State Chebychev oscillation theorem
2) Chebychevs polynomial to find an approximation to a function f(x) given in tabular
form.
Theorem(CHEBYSHEV EQUIOSCILLATION)
Let f(x) be continuous on
[ ] b a,
and P
n
(x) be the best uniform polynomial
approximation. Denote
( ) ( ) ( ) x P x f x f E
n
b x a
n


max ,
and
( ) ( ) ( ) x P x f x
n n

. Then
tere are at least n + 2 points
b x x x x x a
n n
< < < <
+1 2 1 0
.......... ..........
, where
i.
( ) 1 ...., 2 , 1 , 0 , + t n i E x
n i

ii.
( ) ( ) 1 ...., 2 , 1 , 0 ,
1
+
+
n i x x
i i

(1)
Example
Obtain the Chebychevs linear polynomial approximation to the function ( )
3
x x f on
[ ] 1 , 0
.
Solution
P(x) = C
0
+ C
1
(x)
and x
0
= 0 and x
1
= and x
2
= 1.
( ) x C C x x
1 0
3

Using (1) we have
( ) ( )
( ) ( )
( ) 0 3
1
0
1
2 '



c x x
and

66
Thus we have
( )
0 3
0 1 2 1
0 2
1
2
0 1
3
0 1
3

+ +

c x
and
c c x
c c x

which gives
1
1
C ,
3
1

and
9
3
0
C
The Chebychevs linear approximation is given by
( )
9
3
1
x x P
Question
Obtain the Chebychevs polynomial approximation of second degree to the function
( )
3
x x f on
[ ] 1 , 0
.

67
CHOICE OF THE METHOD
1) Understand and use the concept of Extrapolation to the limit.
We have considered various forms of the approximating polynomials. The interpolating
polynomials and the function f(x) agree in value at a set of points x
i
, i = 0, 1, .., n
belonging to an interval
[ ] b a,
. We use this interpolating polynomial to determine the
value of f(x) at any point i
x x
. If
( ) b a x ,
, we call it an interpolating problem,
otherwise it is called an extrapolation problem. Normally interpolating problem produce
better results. The same interpolating polynomial can be used for obtaining roots of f(x),
certain order derivatives of f(x) at tabular or non-tabular points, integral of f(x) between
known limits or for any other operation desired on f(x).
For a given set of tabular data, the Lagrange interpolating polynomial can be easily
obtained. In many applications, the exact number of tabular points to be used to achieve a
certain degree of accuracy is not readily known.
WEEK 13 AND 14
i) Students hand in the assignment
ii) Students take sit in course examination.
68