Is a problem of calculating the root of the polynomial p(x)=ax+b well conditioned for variables a,x and b?

Uriah Molina

Uriah Molina

Answered question

2022-11-02

I have a following task of determining whether this problem is well conditioned. I tried to solve it but I am stuck because I don't know how to understand the last step.
Is a problem of calculating the root of the polynomial p ( x ) = a x + b well conditioned for variables a,x and b?
Here is my attempt:
I calculate maximal relative error of result, denoted with U(a,x,b) where a,x,b are arguments with a relative error not greater than arithmetic precision denoted by ν. Here is equation with distorted data for relative error:
| a ( 1 + ϵ 1 ) x ( 1 + ϵ 2 ) + b ( 1 + ϵ 3 ) a x b | | a x + b | = U ( a , x , b )
And
sup | ϵ | ν U ( a , x , b ) = | a x ( 2 ν + ν 2 ) + b ν | | a x + b |
c o n d ( a , x , b ) = U ( a , x , b ) ν = | a x ( 2 + ν ) + b | | a x + b |
How this translates to statement that problem is well defined or not? I don't specifically understand this step.

Answer & Explanation

Camden Stanton

Camden Stanton

Beginner2022-11-03Added 14 answers

Step 1
We are investigating the sensitivity of the root x = b / a of the linear equation
a x + b = 0
to small changes in the input, i.e., the vector ( a , b ) R 2 and a 0. We need to decide how to measure the size of changes, i.e., what is a small change? I will consider changes that are small relative to the components. To that end, let ϵ > 0 be given and consider perturbations Δ a and Δ b such that
| Δ a | ϵ | a | , | Δ b | ϵ | b | .
We are ultimately interested in the limit where ϵ tends to zero, so there is no harm in assuming that ϵ < 1. Since a 0 we are certain that
a + Δ a 0.
It follows that the perturbed equation
( a + Δ a ) z = b + Δ b
has a unique solution
z = x + Δ x .
Our objective is to determine the largest possible size of the relative error Δ x x and the limiting behavior of the worst case scenario as ϵ tends to zero. From
( a + Δ a ) ( x + Δ x ) = b + Δ b
it follows immediately that
( a + Δ a ) Δ x = b + Δ b a x ( Δ a ) x = Δ b ( Δ a ) x
I now assume that b 0 so that x = b / a 0. Division by x produces
( a + Δ a ) Δ x x = a Δ b b Δ a .
Division by a + Δ a produces
Δ x x = a a + Δ a Δ b b Δ a a + Δ a
We can now start bounding the relative error Δ x x subject to the constraints that
| Δ a | ϵ | a | , | Δ b | ϵ | b | .
By the triangle inequality we have
| Δ x x | | a | | a | ( 1 ϵ ) ϵ + ϵ | a | | a | ( 1 ϵ ) = 2 ϵ 1 ϵ .
It is important to recognize that equality is achieved for the choice of
Δ a = ϵ a , Δ b = ϵ b .
We can now conclude that
sup { 1 ϵ | Δ x x | : ( a + Δ a ) ( x + Δ x ) = ( b + Δ b ) | Δ a | ϵ | a | | Δ b | ϵ | b | } = 2 1 ϵ
This characterizes the worst case behavior under the given constraints. We are interested in the case of small values of ϵ. It is clear that
sup { 1 ϵ | Δ x x | : ( a + Δ a ) ( x + Δ x ) = ( b + Δ b ) | Δ a | ϵ | a | | Δ b | ϵ | b | } 2 , ϵ 0 , ϵ > 0.
We conclude that the root
x = b a
is well-conditioned in the componentwise relative sense. This completes the investigation.
Step 2
Concluding remarks: It is entirely possible to solve this problem by treating x as a function of two variables, i.e.,
x = f ( a , b ) = b a
and invoking the general theory for the condition numbers of functions of multiple variables. But this is overkill and it defeats the purpose of the exercise. The above derivation mirrors the analysis of the solution of the standard linear system A x = b where A R n × n is a nonsingular matrix and b R n .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?