Transcript Presentation13

Numerical Mathematic
Wai Hung, Chan
 Thomas, Nguyen

Numerical Mathematic
Number
Representation
Round off errors
Overflow and Underflow
Classical Numerical Algorithms
Linear Algebra
Number and their representation
– text characters
•Easy read and write of numbers
ASCII
Binary
•
Natural form of computer
Binary Numbering System

The binary number system is similar to the
decimal number system except that
 All values are composed of 0’s and 1’s (instead
of 0-9)
 Each position in a number represents a power
of 2 (instead of a power of 10)
 Decimal: 729 – 7 in the 100’s position and 2 in
the 10’s position and 9 in the 1’s position
 Binary: 1101 – 1 in the 8’s position and 1 in
the 4’s position and 0 in the 2’s position and 1
in the 1’s position
Positive Integer Representations

Convert a binary value to its equivalent
decimal value:
 Examples:
011010102  0*27 + 1*26 + 1*25 +
0*24 + 1*23 + 0*22 + 1*21 + 0*20 =
64 + 32 + 8 + 2 = 10610
Number and their representation
(Cont)
Binary number (base 2)

Things may become complicated
o
o
o

Numbers are finite (overflow)
Fraction and real numbers
Negative numbers
How do we represent negative number?
Representing Negative Integers

Signed Magnitude
Add 1 bit to the number at the leading
end, this will be the sign bit
 Positive numbers sign bit = 0
 Negative numbers sign bit = 1
 Examples:

34 = 00100010
 -34 = 10100010

Representing Negative Integers (Cont)

Two’s Complement
 Improvement over Signed Magnitude because it
doesn’t have either of the problems
 Representation is the same for positive numbers
 For negative numbers, negate the number and then
add 1
 Example:
 42  00101010
 -42  11010101 + 1 = 11010110
 Notice that the leading bit is still a sign bit



+3 = 00000011
+2 = 00000010
+1 = 00000001
-3 = 11111101
-2 = 11111110
-1 = 11111111
Working with 2’s complement


Negate a number
o Invert every single bit (0  1, 10)
o Add 1 to the result
Example
0000 0010
=2
1111 1101
inverted
1111 1110
1 added
=-2
0000 0001
0000 0010
inverted
1 added
=2
Round off errors


Any computer can only retain a finite number of
significant digit to represent the results of an
operation. When an result can not be represent
exactly, a round off error introduced.
These are the errors the computer make in doing
arithmetic. (For example, the error a computer or
calculator makes in evaluating (1/3 + 1/7)). Even
if we have a good formula to solve a problem it
may not produce good answers when it evaluated
on a computer.
Round off errors (Cont)

Computers make small error when
they do arithmetic.
For example:
11 * (15/11) -15 = 0 (?)
Overflow and Underflow

Overflow:
If the result of a computation is larger than that
allowed by the computer you have an overflow.

Underflow:
In computing, a condition occurring when a
machine calculation produces a non-zero result that
is smaller than the smallest non-zero quantity that
the machine's storage unit is capable of storing or
representing.
Example: 58 – 83 = -25
1.
Convert
58 = 0011 1010
83 = 0101 0011
2.
Get 2’s complement
0101 0011
1010 1100
+1
1010 1101
3.
Original number (83)
Flip the bits
Add 1
2’s complement
Add the two numbers:
0011 1010
+ 1010 1101
1110 0111
=58
2’s complement of 83
Answer = -25 (No
Overflow)
Overflow (Cont)

The sum of two unsigned numbers can
exceed any representation
+
0101 0011 = 83
0010 1111 = 47
1000 0010 = -126 (Overflow)
Detecting Overflow
No overflow when adding a +ve and a -ve
number.
 No overflow when sign are the same for
subtraction.
 Overflow when adding two positive yields a
negative
 Or, adding two negative give a positive
 Or, subtract a negative from a positive
and get a negative
 Or, subtract a positive from a negative
and get a positive

Overflow (Cont)
General Overflow Condition
Operation
A+B
A+B
A–B
A–B
Condition
A>0 B>0
A<0 B<0
A>0 B<0
A<0 B>0
Result
<0
>0
<0
>0
Sources




http://wwwmaths.anu.edu.au/DoM/secondyear/MATH2501/lect-054.pdf
http://www.maths.uq.edu.au/~gac/math2200/mn_roff.pdf
http://lapwww.epfl.ch/courses/archord1/Computer%20Arithmetic.pdf
http://www.cse.psu.edu/~cg575/lectures/cse575-fpops.pdf
CLASSICAL NUMERICAL
ALGORITHM
 TRAPEZOID RULE:
  (a to b) (x) dx  Tn = x/2 [(Xo) + 2 (X1) +

2(X2) +….+ 2 (Xn -1) + 2 (Xn)
where x = (b - a) /n and Xi = a + i x.
example : Use trapezoid rule with n=5 to
approximate integral (1 to 2) (1/x) dx
with n=5, a =1, and b=2, we have x =(2-1)/5=0.2

(1to 2) 1/x dx T5 = .2/2[(1)+ 2(1.2)+….. (2)




= .1[1/1 + 2/1.2 + 2/1.4+ 2/1.6 +..+1/2]
 0.695635


MIDPOINT RULE:
 (a to b) (x) dx  Mn = x [(X1) + (X2) +

+….+ (Xn) where
x = (b - a) /n and Xi =1/2(Xi-1+Xi) =
midpoint[Xi-1, Xi]
example : Use midpoint rule with n=5 to
approximate integral (1 to 2) (1/x) dx
with n=5, a =1, and b=2, we have x =(2-1)/5=0.2

(1to 2) 1/x dx = 1/5 [(1.1)+ 2(1.3)+….. (1.9)





= 0.2[1/1.1 + 2/1.3 + 2/1.4+ 2/1.5 +..+1/1.9]
 0.691908
SIMPSON’S RULE

 (a to b) (x) dx  Sn = x/3 [(Xo) + 4 (X1) +

2(X2) + 4(X3) +2(Xn -2) + 4(Xn -1)+(Xn)]
where n is even and x = (b - a) / n
Example: use simpson’s rule to approximate

 (1 to 2) (1/x) dx with n=10.

We have x =1/10=0.1
 (1 to 2) (1/x) dx  S10 = x/3 [(1)+4(1.1)+


2(1.2)+ 4(1.3)+…..+ 2(1.8)+4(1.9)+ (2)
= 0.1/3 [1/1 + 4/1.1 + 2/1/2 + 4/1.3 + 2/1.4 + 4/1.5
+ 2/1.6 + 4/1.7 + 2/1.8 + 4/1.9 + 1/2]
 0.0.693135
LINEAR EQUATION
1. Introduction to linear equations
 A linear equation in n unknowns x1; x2; … xn is
an equation of the form:
 a1x1 + a2x2 + + anxn = b;
 where a1; a2; : : : ; an= b are given real numbers.
 For example, with x and y instead of x1 and x2,
the linear equation 2x + 3y = 6 describes the line
passing through the points (3; 0) and (0; 2).
 A system of m linear equations in n unknowns x1;
x2; ; xn is a family of linear equations
a11 x1 + a12 x2 + .... + a1n xn = b1
a21 x1 + a22 x2 + …. + a2n xn = b2
...
am1 x1 + am2 x2 + .. + amn xn = bm:
INTRO(CONT)



Note that the above system can be written
concisely as j=1
Σ (i=1 to m) aij xj = bi; i = 1; 2; ; m:
The matrix:
a11 a12
a1n
a21 a22
a2n
...
am1 am2
amn
is called the coefficient matrix of the system,
while the matrix
a11 a12 a1n
b1
a21 a22 a2n
b2
…
..
am1 am2 amn
bm
EXAMPLE : Find a polynomial of the form y =
a0+a1x+a2x^2+a3x^3
which passes through the points (-3, -2), (-1, -2), (2, 1).


Solution. When x has the values -3;-1; 1; 2, then y
takes corresponding values -2; 2; 5; 1 and we get
four equations in the unknowns a0; a1; a2; a3.
a0 - 3a1 + 9a2- 27a3 = -2
a0 - a1 + a2 - a3 = 2
a0 + a1 + a2
+ a3 = 5
a0 + 2a1 + 4a2 + 8a3 = 1:
This system has the unique solution a0 = 93/20;
a1 = 221/120; a2 =
-23/20; a3 = -41/120. So the required polynomial
is:
y = 93/20 +221/20x –23/20x^2-41/20x^3
Solving linear equations


DEFINITION : (Row echelon form) A matrix is in row
echelon form if
(i) all zero rows (if any) are at the bottom of the
matrix
(ii) if two successive rows are non zero, the second row
starts with more zeros than the first (moving from left
to right).
For example:
the matrix is in row echelon form
0100
0010
0000
0000
The matrix is not in row echelon form
0100
0100
0000
0000
The zero matrix of any size is always in row echelon form.
DEFINITION: (Reduced row echelon form) A matrix
is in reduced row echelon form if
(i). it is in row echelon form
(ii). the leading (leftmost nonzero) entry in each non
zero row is 1,
(iii). all other elements of the column in which the
leading entry 1 occurs are zeros.

For example:
1 0

0 1


012002
000103


14
0000
000000
DEFINITION (Elementary row operations) There are
three types of elementary row operations that can be
performed on matrices:
1. Interchanging two rows:
Ri <-> Rj
interchanges rows i and j.
2. Multiplying a row by a nonzero scalar: Ri -> t
Ri multiplies row i by the nonzero scalar t.
3. Adding a multiple of one row to another row:
Rj -> Rj + tRi adds t times row i to row j.

1 2 0
1 2 0
 A=
2 1 1
R2-->R2 +2R3
4 -1 5

1 -1 -2
1 -1 2

1 2 0
2 4 0
 R2<-->R3
1 -1 2
R1-->2R1
1 -1 2 =B

4 -1 5
4 -1 5
The Gauss-Jordan algorithm

This is a process which starts with a given matrix A and produces
a matrix B in reduced row echelon form, which is row equivalent
to A. If A is the augmented matrix of a system of linear equations,
then B will be a much simpler matrix than A

STEP 1. :Find the first nonzero column moving from left to
right, (column c1) and select a non zero entry from this column. By
interchanging rows, if necessary, ensure that the first entry in this
column is nonzero. Multiply row 1 by the multiplicative inverse of
a1c1 thereby converting a1c1 to 1. For each non zero element aic1
; i > 1, (if any) in column c1, add -aic1,time row 1 to row I, thereby,
we can find all element in column c1 is apart from the first zero.

STEP 2. : If the matrix obtained at Step 1 has its 2nd; : : : ;mth
rows all zero, the matrix is in reduced row echelon form.
Otherwise suppose that the rst column which has a non zero
element in the rows below the rst is column c2. Then c1 < c2. By
interchanging rows below the first, if necessary, ensure that a2c2 is
non{zero. Then convert a2c2 to 1 and by adding suitable multiples
of row 2 to the remaning rows, where necessary, ensure that all
remaining elements in column c2 are zero.
EXAMPLE



00 4 0
5/2
2 2 -2 5
0
5 5 -1 5
R1 <->R2


R3 ->R3-5R1

2 2 -2 5
1 1 -1
0 0 4 0
0 0 4
5 5 -1 5
1 1 -1 5/2
0 0 4 2
0 0 4 -15/2
R1->-1/2 R1 5 5 -1 5
R2->1/4R2
1 1 -1 5/2
0 0 1 0
0 0 4 -15/2




R1->R1 + R2
1 1 0
5/2
5/2
R3->R3- 4R2 0 0 1 0 R3->-2/15R3
0
0 0 0 -15/2
1
1 1 0
0 0 1
0 0 0
MATRICES

Matrix arithmetic

Matrices will usually be denoted by capital letters
and the equation A = [aij ] means that the element
in the ith row and jth column of the matrix A
equals aij . It is also occasionally convenient to
write aij = (A)ij . For the present all matrices will
have rational entries, unless otherwise stated.

EXAMPLE 2.1.1 The formula aij = 1/(i + j) for
1<=i<=3; 1<= j<= 4, defines a 3x4 matrix A = [aij ],
namely
1/2 1/3 1/4 1/5
A =
1/3 1/4 1/5 1/6
1/4 1/5 1/6 1/7






DEFINITION:(Equality of matrices) Matrices A and
B are said to be equal if A and B have the same size
and corresponding elements are equal; that is A and B
є Mmxn(F) and A = [aij ]; B = [bij ], with aij = bij for
1<= i <= m; 1<= j<= n.
DEFINITION:(Addition of matrices) Let A = [aij ]
and B =[bij] be of the same size. Then A + B is the
matrix obtained by adding corresponding elements of
A and B; that is A + B = [aij ] + [bij ] = [aij + bij ].
DEFINITION :(Scalar multiple of a matrix) Let A =
[aij ] and t є F (that is t is a Scalar). Then tA is the
matrix obtained by multiplying all elements of A by t;
that is tA = t[aij ] = [taij ].



DEFINITION 2.1.4 (Additive inverse of a matrix)
Let A = [aij ] .Then ¡A is the matrix obtained by
replacing the elements of A by their additive
inverses; that is A = -[aij ] = [-aij ]:
DEFINITION 2.1.5 (Subtraction of matrices)
Matrix subtraction is defined for two matrices A =
[aij ] and B = [bij ] of the same size, in the usual
way; that is A - B = [aij ] - [bij ] = [aij - bij ]:
DEFINITION 2.1.6 (The zero matrix) For each m;
n the matrix inMmxn(F), all of whose elements
are zero, is called the zero matrix (of size mxn)
and is denoted by the symbol 0.

The matrix operations of addition, scalar
multiplication, additive inverse and
subtraction satisfy the usual laws of
arithmetic.
1. (A + B) + C = A + (B + C);
 2. A + B = B + A;
 3. 0 + A = A;
 4. A + (-A) = 0;
 5. (s + t)A = sA + tA, (s x t)A = sA x tA;
 6. t(A + B) = tA + tB, t(A + B) = tA + tB;
 7. s(tA) = (st)A;
 8. 1A = A, 0A = 0, (-1)A = -A;








DEFINITION: (Matrix product) Let A = [aij ] be
a matrix of size m x n and B = [bjk] be a matrix
of size n x p; (that is the number of columns of A
equals the number of rows of B). Then AB is the
m x p matrix C = [cik] whose (i, k)th element is
defined by the formula:
cik = Σ(j=1 to n) aijbjk = ai1*b1k + .. + ain*bnk.
Example:
1 2 5 6 = 1*5 +2*7 1*6 +2*8 = 19 22
3 4 7 8
385 +4*7 3*6 +4*8
43 50
5 6 1 2
23 34
1 2 5 6
7 8 3 4 = 41 46 =
3 4 7 8
Matrix product (cont)





Matrix multiplication obeys many of the familiar
laws of arithmetic apart from the commutative
law.
1. (AB)C = A(BC) if A; B; C are mxn; nxp; pxq,
respectively;
2. t(AB) = (tA)B = A(tB), A(-B) = (-A)B = -(AB);
3. (A + B)C = AC + BC if A and B are mxn and C
is nxp;
4. D(A + B) = DA + DB if A and B are mxn and D
is pxm.









Example:
Let A, B, C, D be matrices defined by
A = 3 0
B= 1 5 2
C = -3 -1
-1 2
-1 1 0
2 1
1 1
-4 1 3
4 3
C = 4 -1
2 0
Which of the following matrices are defined?
A + B; A + C; AB; BA; CD; DC; D^2:
THEOREM (Cramer's rule for 2 equations in
2 unknowns)









The system:
ax + by = e
cx + dy = f a b
has a unique solution if Δ = c d = 0 namely
X= Δ1/Δ, Y= Δ2/Δ where Δ1 = e b , Δ2 = a e
f d
c f
EXAMPLE : the system 7x + 8y = 100
2x - 9y = 10
Δ= 7 8
Δ1= 100 8
Δ2= 7 100
2 -9 = -79
10 9 =-980 2 10 =-130
So the system has unique solution
X = 980 / 79 , Y = 130 / 79
DETERMINANTS




DEFINITION: If A = a11
a12
a21
a22 ¸ we define the
determinant of A, (also denoted by det A,) to be
the scalar det A = a11*a22 - a12*a21:
DEFINITION: (Minor) Let Mij(A) (or simply Mij
if there is no ambiguity) denote the determinant of
the (n -1) and (n - 1) sub matrix of A formed by
deleting the ith row and jth column of A. (Mij(A)
is called the (i, j) minor of A.)
The determinant function has been defined for
matrices of size (n-1)x(n-1). Then det A is defined
by the so called first-row Laplace expansion.







detA = a11M11(A) - a12 M12(A) + ……. +
(-1)^1+n M1n(A)
= Σ(j=1 to n) (-1)^1+j a1j M1j(A):
For example: if A = [aij ] is a 3 x 3 matrix, the
Laplace expansion gives:
detA = a11 M11(A) - a12 M12(A) + a13 M13(A)
= a11(a22a33 - a23a32) - a12(a21a33a23a31) + a13(a21a32 - a22a31)
= a11a22a33 - a11a23a32 - a12a21a33 +
a12a23a31 + a13a21a32 - a13a22a31
THEOREM: Let A = [aij ], where aij = 0 if i <
j. Then detA = a11*a22*…*ann, an important
special case is when A is a diagonal matrix.









a11 0 0 0 ... 0
a21 a22 …...….0
det A =
…
a33
0
an1 an2 ……ann
det A = a11 (a22………ann)
1 0 0 0
det A =
3 3 0 0 = 18
4 3 3 0
1 3 4 2
THEOREM: detA = Σ (j=1 to n) (-1)^i+j aij Mij(A)
for i = 1,.,n (the so-called i-th row expansion) and
detA = Σ(i=1to n)(-1)^i+j aij Mij(A)
for j= 1,...,n(the so-called j-th column expansion).






The expression (-1)i+j obeys the chess board
pattern of signs:
+ - + - …….
- + - +…….
+ - + - ……
.
.








DEFINITION: (Cofactor) The (i, j) cofactor of A,
denoted by Cij(A) (or Cij if there is no ambiguity)
is defined by Cij(A) = (-1)^i+j Mij(A).
DEFINITION: (Adjoint) If A = [aij ] is an nxn
matrix, the ad-joint of A, denoted by adjA, is the
transpose of the matrix of cofactors.
C11 C21 ….. Cn1
adj A =
C12 C22 …. Cn2
..
…..
C1n C2n …..Cnn
THEOREM: Let A be an n x n matrix. Then
A(adjA) = (adjA)A.











If detA = 0, then A is nonsingular and
A^-1 = (1/ detA) adj A.
Example:
1 2 3
det A =
4 5 6
= -3 =
7 8 9
C11 C21 C31
A^-1 = - 1/3 C12 C22 C32
C13 C23 C33
-3
6 -3
A^-1 = -1/3
12 -15 6
-8
8 -3
0
EIGENVALUES AND
EIGENVECTORS

Motivation:

We motivate the chapter on eigenvalues by
discussing the equation: ax^2 + 2hxy + by^2 =
c
where not all of a; h; b are zero. The expression
ax2 + 2hxy + by2 is called a quadratic form in x
and y and we have the identity
ax^2 + 2hxy + by^2 = x y a h x = X^t AX
h b y
where X = x
a h
y and A = h b . A is called the
matrix of the quadratic form.






A has characteristic equation:

λ² - (a+b) λ + ab - h² = 0

this called eigenvalue equation of the matrix A.

DEFINITION (Eigenvalue, eigenvector)
Let A be a complex square matrix. Then if ¸λ is a

complex number and X a non-zero complex
column vector satisfying AX = λX, we call X an

eigenvector of A, while ¸ λ is called an eigenvalue
of A.

if ¸ λ is an eigenvalue of an nxn matrix A, with

corresponding eigenvector X, then (A -λIn)X = 0,
with X = 0, so det (A - λIn) = 0 and there are at
most n distinct eigenvalues of A.




EXAMPLE: Find the eigenvalues and eigenvectors of A = 2 1
1 2
Solution. The characteristic equation of A is
λ² - 4 λ + 3 = 0, or (λ - 1)(λ - 3) = 0
 Hence λ = 1 or 3. The eigenvector equation
(A - λ In)X = 0 reduces to 2-λ 1 x
0

1 2- λ y = 0
 or (2 - λ)x + y = 0

x + (2 - λ)y = 0:
 Taking λ =1 give x + y = 0

x + y= 0


Which has solution x = -y, y arbitrary.
Consequently the eigenvectors corresponding
to λ = 1 are the vectors -y with y = 0

y
 Taking λ = 3 give -x + y = 0

x + y= 0
 which has solution x = y, y arbitrary.
Consequently the eigenvectors corresponding to
 λ = 3 are the vectors
y with y = 0

y

Reference sources

www.maths.uq.edu.au/~krm/ela.html