Well-Conditioned Systems of Equations
Autar Kaw
Humberto Isaza
http://nm.MathForCollege.com
Transforming Numerical Methods Education for STEM Undergraduates
http://nm.MathForCollege.com
1.
differentiate between ill-conditioned and well-conditioned systems of equations,
2.
define the norm of a matrix,
3.
define the condition number of a square matrix,
4.
relate the condition number to the ill or well conditioning of a system of equations,
that is, determine how much trust you can trust the solution of a set of equations.
What do you mean by ill-conditioned and well-conditioned system of equations?
A system of equations is considered to be
well-conditioned
if a small change in the
coefficient matrix or a small change in the right hand side results in a small change
in the solution vector.
A system of equations is considered to be
ill-conditioned
if a small change in the
coefficient matrix or a small change in the right hand side results in a large change in
the solution vector.
Is this system of equations well-conditioned?
Solution
The solution to the set of equations is
Make a small change in the right hand side vector of the equations
gives
Make a small change in the coefficient matrix of the equations
gives
This last systems of equation “looks” ill-conditioned because a small
change in the coefficient matrix or the right hand side resulted in a large
change in the solution vector.
Is this system of equations well-conditioned?
Solution
The solution to the previous equations is
Make a small change in the right hand side vector of the equations.
gives
Make a small change in the coefficient matrix of the equations.
gives
This system of equation “looks” well conditioned because small
changes in the coefficient matrix or the right hand side resulted in
small changes in the solution vector.
So what if the system of equations is ill conditioned or well conditioned?
Well-conditioned and ill-conditioned
Well, if a system of equations is ill-conditioned, we cannot trust the solution
as much. Revisit the
velocity problem, Example 5.1 in Chapter 5.
The values
in the coefficient matrix
are squares of time, etc. For example, if instead
of you used would you want this small change to
make a huge difference in the solution vector. If it did, would you trust the
solution?
Later we will see how much (quantifiable terms) we can trust the solution in a
system of equations. Every invertible square matrix has a
condition number
and coupled with the
machine epsilon
, we can quantify how many
significant digits one can trust in the solution.
To calculate the condition number of an invertible square matrix, I need to know
what the norm of a matrix means. How is the norm of a matrix defined?
Just like the determinant, the norm of a matrix is a simple unique scalar number.
However, the norm is always positive and is defined for all matrices – square or
rectangular, and invertible or noninvertible square matrices.
One of the popular definitions of a norm is the row
sum norm (also called the
uniform-matrix norm). For a matrix , the row sum norm of is defined
as
that is, find the sum of the absolute value of the elements of each row of the matrix .
The maximum out of the such values is the row sum norm of the matrix .
Find the row sum norm of the following matrix [A].
Solution
Let us start answering this question using an example. Go back to the
ill-conditioned
system of equations,
that gives the solution as
Denoting the above set of equations as
Making a small change in the right hand side,
gives,
Denoting the above set of equations by
right hand side vector is found by
and the change in the solution vector is found by
then
and
then
The relative change in the norm of the solution vector is
The relative change in the norm of the right hand side vector is
Let us now go back to the
well-conditioned
system of equations.
Gives
Denoting the system of equations by
Making a small change in the right hand side vector
Gives
Denoting the above set of equations by
the change in the right hand side vector is then found by
and the change in the solution vector is
then
and
then
The relative change in the norm of solution vector is
The relative change in the norm of the right hand side vector is
See the small relative change the right hand side vector of results in the
small relative change in the solution vector of
In fact, the ratio between the relative change in the norm of the solution vector and the
relative change in the norm of the right hand side vector is
What are some properties of norms?
1.
For a matrix ,
2.
For a matrix and a scalar k,
3.
For two matrices and of same order,
4.
For two matrices and that can be multiplied as ,
Is there a general relationship that exists between and or
between and ? If so, it could help us identify well-conditioned
and ill conditioned system of equations.
If there is such a relationship, will it help us quantify the conditioning of the
matrix? That is, will it tell us how many significant digits we could trust in
the solution of a system of simultaneous linear equations?
there is a relationship that exists between
and between
these relationships are
and
the above two inequalities show that the relative change in the norm of the right hand
side vector or the coefficient matrix can be amplified by as much as .
This number is called the
condition number
of the matrix and coupled with
the machine epsilon, we can quantify the accuracy of the solution of
Proof for
that
Proof
let
(1)
then is changed to the will change to such that
(2)
From Equations (1) and (2),
Denoting change in and matrices as and , respectively
then
Expanding the previous expression
Applying the theorem of norms, that the norm of multiplied matrices is less than the
multiplication of the individual norms of the matrices,
Multiplying both sides by
How do I use the above theorems to find how many significant digits are correct
in my solution vector?
the relative error in a solution vector is Cond (A) relative error in right hand side.
the possible relative error in the solution vector is Cond (A)
Hence Cond (A) should give us the number of significant digits,
m
at least
correct in our solution by comparing it with
How many significant digits can I trust in the solution of the following system of
equations?
Solution
For
it can be show
Assuming single precision with 24 bits used in the mantissa for real numbers, the
machine epsilon is
comparing it with
So two significant digits are at least correct in the solution vector.
How many significant digits can I trust in the solution of the following system of
equations?
Solution
For
It can be shown
Then
Assuming single precision with 24 bits used in the mantissa for real numbers, the
machine epsilon
Comparing it with
So five significant digits are at least correct in the solution vector.
Ill-Conditioned matrix
Well-Conditioned matrix
Norm
Condition Number
Machine Epsilon
Significant Digits
Concepts of ill-conditioned and well-conditioned systems of equations, the impact of small changes in coefficient matrices, and how to determine if a system is well-conditioned or ill-conditioned through numerical methods. This includes examples and explanations to enhance your understanding of the topic.
Uploaded on Feb 25, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Autar Kaw Humberto Isaza http://nm.MathForCollege.com Transforming Numerical Methods Education for STEM Undergraduates
1. differentiate between ill-conditioned and well-conditioned systems of equations, 2. define the norm of a matrix, 3. define the condition number of a square matrix, 4. relate the condition number to the ill or well conditioning of a system of equations, that is, determine how much trust you can trust the solution of a set of equations.
What do you mean by ill-conditioned and well-conditioned system of equations? A system of equations is considered to be well-conditioned if a small change in the coefficient matrix or a small change in the right hand side results in a small change in the solution vector. A system of equations is considered to be ill-conditioned if a small change in the coefficient matrix or a small change in the right hand side results in a large change in the solution vector.
Is this system of equations well-conditioned? 1 2 4 x = . 7 2 . 3 999 999 y
Solution The solution to the set of equations is 2 x = 1 y Make a small change in the right hand side vector of the equations 1 2 . 4 001 x = . 7 2 . 3 999 998 y gives . 3 999 x = . 4 000 y
Make a small change in the coefficient matrix of the equations . 1 001 . 2 001 4 x = . 7 . 2 001 . 3 998 999 y gives . 3 994 x = . 0 001388 y This last systems of equation looks ill-conditioned because a small change in the coefficient matrix or the right hand side resulted in a large change in the solution vector.
Is this system of equations well-conditioned? 1 2 4 x = 2 3 7 y
Solution The solution to the previous equations is 2 x = 1 y Make a small change in the right hand side vector of the equations. 1 2 . 4 001 x = 2 3 . 7 001 y gives . 1 999 x = . 1 001 y
Make a small change in the coefficient matrix of the equations. . 1 001 . 2 001 4 x = . 2 001 . 3 001 7 y gives . 2 003 x = . 0 997 y This system of equation looks well conditioned because small changes in the coefficient matrix or the right hand side resulted in small changes in the solution vector.
So what if the system of equations is ill conditioned or well conditioned? Well, if a system of equations is ill-conditioned, we cannot trust the solution as much. Revisit the velocity problem, Example 5.1 in Chapter 5. The values in the coefficient matrix are squares of time, etc. For example, if instead of you used would you want this small change to make a huge difference in the solution vector. If it did, would you trust the solution? [A ] 11= a 24 99 . , 11= a 25 , Later we will see how much (quantifiable terms) we can trust the solution in a system of equations. Every invertible square matrix has a condition number and coupled with the machine epsilon, we can quantify how many significant digits one can trust in the solution.
To calculate the condition number of an invertible square matrix, I need to know what the norm of a matrix means. How is the norm of a matrix defined? Just like the determinant, the norm of a matrix is a simple unique scalar number. However, the norm is always positive and is defined for all matrices square or rectangular, and invertible or noninvertible square matrices. One of the popular definitions of a norm is the rowsum norm (also called the uniform-matrix norm). For a matrix , the row sum norm of is defined as = j m i 1 1 m [A ] [A ] n max n = A a ij that is, find the sum of the absolute value of the elements of each row of the matrix . The maximum out of the such values is the row sum norm of the matrix .
Find the row sum norm of the following matrix [A]. 099 . 2 10 7 0 = 3 6 A 5 1 5 Solution max i 3 = j = A a ij 1 3 1 ( )( , )( , ) = + + + + + + max 10 7 0 3 . 2 099 6 5 1 5 ( ) ( , ) ( , ) = + + + + + + max 10 7 0 3 . 2 099 6 5 1 5 17 = max , 11 099 . , 11 = 17 .
Let us start answering this question using an example. Go back to the ill-conditioned system of equations, 1 2 4 x = . 7 2 . 3 999 999 y that gives the solution as 2 x = 1 y Denoting the above set of equations as X A = C = 2 X = . 7 999 C
Making a small change in the right hand side, 1 2 . 4 001 x = . 7 2 . 3 999 998 y gives, . 3 999 x = . 4 000 y Denoting the above set of equations by ' ' X A = C right hand side vector is found by C = ' C C and the change in the solution vector is found by X = ' X X
then . 4 001 4 = C . 7 . 7 998 999 . 0 001 = . 0 001 and . 3 999 2 = X . 4 000 1 . 5 999 = . 3 000 then = . 0 001 C = . 5 999 X
The relative change in the norm of the solution vector is X . 5 999 = 2 X = 9995 . 2 The relative change in the norm of the right hand side vector is C C . 0 001 = . 7 999 . 1 = 4 250 10
See the small relative change of 1.250 104 in the right hand side vector results in a large relative change in the solution vector as 2.9995. In fact, the ratio between the relative change in the norm of the solution vector and the relative change in the norm of the right hand side vector is / X X . 2 9995 = 4 / C C . 1 250 10 = 23993
Let us now go back to the well-conditioned system of equations. 1 2 4 x = 2 3 7 y Gives 2 x = 1 y Denoting the system of equations by X A = C = 2 X = 7 C
Making a small change in the right hand side vector 1 2 . 4 001 x = 2 3 . 7 001 y Gives . 1 999 x = . 1 001 y Denoting the above set of equations by ' ' X A = C the change in the right hand side vector is then found by C = ' C C
and the change in the solution vector is X X = ' X then . 4 001 4 = C . 7 001 7 . 0 001 = . 0 001 and . 1 999 2 = X . 1 001 1 . 0 001 = . 0 001
then = . 0 001 C = . 0 001 X The relative change in the norm of solution vector is X . 0 001 = 2 X = 4 5 10 The relative change in the norm of the right hand side vector is C C . 0 001 = 7 . 1 = 4 429 10
See the small relative change the right hand side vector of small relative change in the solution vector of results in the 4 . 1 429 10 4 5 10 In fact, the ratio between the relative change in the norm of the solution vector and the relative change in the norm of the right hand side vector is 4 / X X 5 10 = 4 / C C 1 429 . 10 = 5 . 3
What are some properties of norms? For a matrix , For a matrix and a scalar k, For two matrices and of same order, For two matrices and that can be multiplied as , ] [A ] [B [A [A ] ] 0 1. 2. 3. 4. A kA = k A [A ] [B ] + + A B A B [ [ ] A ] AB A B B
Is there a general relationship that exists between between and ? If so, it could help us identify well-conditioned and ill conditioned system of equations. and or C / X / X C X / A / X A If there is such a relationship, will it help us quantify the conditioning of the matrix? That is, will it tell us how many significant digits we could trust in the solution of a system of simultaneous linear equations?
there is a relationship that exists between X C and X C and between X A and X A these relationships are X C 1 A A + X X C
and X A 1 A A X A the above two inequalities show that the relative change in the norm of the right hand side vector or the coefficient matrix can be amplified by as much as . 1 A A This number is called the condition number of the matrix and coupled with the machine epsilon, we can quantify the accuracy of the solution of 1 A A = [ [ ] A ] [ ] X C
= Proof for [ [ ] A ] [ ] X C that X A 1 A A + X X A Proof let A = X C (1) then is changed to the will change to such that ] [A ' A [X ' X ] X A ' ' (2) = C
From Equations (1) and (2), ' X A = ' X A Denoting change in and matrices as and , respectively ] [A ] [X A X A A = ' A X = ' X X then A ( A ) ( X ) = + + X A X
Expanding the previous expression X A X A = X A + = ] 0 [ A X A = A X = X A ) X ) ) X + + + A ( X A ( X + ( X A X A X + X 1 + Applying the theorem of norms, that the norm of multiplied matrices is less than the multiplication of the individual norms of the matrices, 1 + X A A X X
Multiplying both sides by A 1 + A X A A A X X X A 1 A A + X X A How do I use the above theorems to find how many significant digits are correct in my solution vector? the relative error in a solution vector is Cond (A) relative error in right hand side. the possible relative error in the solution vector is Cond (A) mach Hence Cond (A) correct in our solution by comparing it with should give us the number of significant digits, m at least m 10 5 . 0 mach
How many significant digits can I trust in the solution of the following system of equations? 1 2 2 x = 2 . 3 999 4 y
Solution For 1 2 A = 2 . 3 999 it can be show 3999 2000 A 1 = 2000 1000 = . 5 999 A = 1 5999 A ( ) A = 1 Cond A A = . 5 999 5999 4 . = 35990
Assuming single precision with 24 bits used in the mantissa for real numbers, the machine epsilon is = 1 24 2 mach = 6 119209 . 0 10 = 119209 . 0 6 ( ) 35990 10 Cond A mach 4290 . 0 = 2 10 comparing it with 10 m 5 . 0 4290 . 0 2 m 5 . 0 10 10 2 m So two significant digits are at least correct in the solution vector.
How many significant digits can I trust in the solution of the following system of equations? 1 2 4 x = 2 3 7 y
Solution For 1 2 A = 2 3 It can be shown 3 2 A 1 = 2 1 Then = 5 A = 1 5 A = 1 Cond (A) A A = = 5 25 5
Assuming single precision with 24 bits used in the mantissa for real numbers, the machine epsilon 24 12 = mach 6 10 119209 . 0 = 10 119209 . 0 25 ) ( = mach A Cond 5 10 2980 . 0 = 6 10 m Comparing it with 5 . 0 2980 . 0 m 5 m 5 . 0 10 10 5 So five significant digits are at least correct in the solution vector.
Ill-Conditioned matrix Well-Conditioned matrix Norm Condition Number Machine Epsilon Significant Digits
