numerical methods for non-linear equations

[PG1995]

Hi

Could you please help me with **broken link removed** queries about Muller's method? I'm sorry I couldn't understand any of those parts. And you don't need to give any in-depth explanation. You can just tell me what is being done there. Thank you.

Regards
PG

 

[steveB]

For Q1, the term "distinct point" probably just means that all three points are different, in that no two of them are the same. This will surely define a quadratic shape. You are correct that they might turn out to be co-linear, but in that case the coefficient "a" will turn out to be zero. Hence, their wording seems perfectly fine, in my opinion.

I'll look at the other questions later.

 

[PG1995]

Thanks for the reply.

I'll look at the other questions later.

No problem. Take your time.

Best wishes
PG

 

[steveB]

For Q2, I think we need to start by asking you whether you are required to fully understand the full derivation of the book? Or, if you are only required to understand how to use the method and the basic idea by which the method works?

I say this because it seems you have not studied the linear algebra and matrix manipulation techniques yet. If that is true, then any attempt to try and help you is going to amount to trying to give you a crash course in linear algebra. This is not practical. I can try to give a basic overview, but I'm not prepared to go down the laborious path of answering the myriad of additional question that will naturally follow. I think it is better for you to just understand the gist of what is being done, and be able to use the method. If your teacher requires a full understanding of what is in the book, then the it's his job to teach you the background needed.

That said, basically the matrix equation is not a system of quadratic equations as you said. Even though the quadratic equation is the origin of the numbers in the matrix, this is a linear equation set. Normally, you could directly solve for a, b and c with three linear equations (the bottom three equations in the matrix). Then you could use a, b and c to express the quadratic function, and then you could do a root solve on this. However, the book is presenting a slick method of avoiding the calculation of a, b and c directly. And, this method comes from linear algebra. Basically, by using 4 equations, where only three equations are independent, the only way to get a nontrivial solution is if the determinant is zero. The determinant is a well known operation on a matrix from linear algebra, and it is easy to calculate for 2x2, 3x3 and 4x4 matrices (more difficult for larger ones). By setting the determinant to zero, and then setting "f" to zero, one finds the root for the quadratic. Then, by iterating, the root for the quadratic converges to the root of the real equation you are trying to solve.

This is the basics of what is happening, and if the linear algebra is unfamiliar, you could use other methods that you are familiar with. However, the equations get quite involved and it will not be easy for you to match up your method with the form given in the book. Still, your method would work, if you derive it without mistakes.

For Q3, you asked two things ...

First you asked, "how do you get a better approximation to the root". Well, just like the secant method (or other methods), each iteration is usually better and better as you get closer to the root. This is assuming the method converges. However, you can find examples that would not converge and you can find examples that might initially get worse, and then get better after a few iterations.

Second, you asked, "where does expression 2.30 come from". Well, this expression comes directly from the definition of λ in equation 2.22. Just rearrange it using simple algebra.

 

[PG1995]

Thank you very much for the reply.

I think we need to start by asking you whether you are required to fully understand the full derivation of the book? Or, if you are only required to understand how to use the method and the basic idea by which the method works?

No, I'm only required to understand how to use the method. But I would like to understand the method itself at some later stage. Thanks.

Best wishes
PG

 

[MrAl]

Hi,


Finally made it back from the storm


Q1:
Dont fret over this too much. When they talk like that it's because in the more
general case we have a quadratic and not a straight line, because in ideas like
this one it is as if there is no such thing as a straight line. If it was a
straight line you wouldnt need this method
Also note that a straight line could be considered just a degenerate case of the
quadratic:
a*x^2+b*x+c=d
and with a very small 'a' we have:
bx+c=d
but to make this a quadratic we only need include a very very small 'a':
1e-12*x^2+b*x+c=d
and then instead of a straight line we have an approximation to a straight line
using a quadratic. So we can view every line as being a quadratic especially
since it will be very rare to find an actual straight line in this context.
[Strictly speaking 'a' would be very small relative to the other constants and 1e-12
is just a simple example].

Q2:
Equation 2.19 is better known as Lagrange's Interpolation Formula (for just
three points) and can be obtained in a much simpler manner.
They are just using simultaneous equations to find the unknown variables. That is
all that it is and nothing more. It doesnt matter that it is a quadratic. The
only thing that matters is that we find a, b, and c.
Using the equation:
a*x^2+b*x+c=f

we just repeat that as many times as needed. We need to find three variables so
we need to repeat this three times. For each equation we use one point (x,f) which
we usually write (x,y) but here they are using 'f' as the function value at x.
So we pick three points:
(x1,f1), (x2,f2), (x3,f3)

and we use them in the equation above forming three equations:
a*x1^2+b*x1+c=f1
a*x2^2+b*x2+c=f2
a*x3^2+b*x3+c=f3

and this is now just a set of linear equations because x1, x2, x3, and f1, f2, and f3
are all constants and we only need to find the variables a, b, and c.
So there are many methods you can use there to find a,b,c and you should get the same
results if you just solve for a,b,c and then plugging the solutions back into the
equation and then factoring, simplifying, etc. It may not be easy though.
You could also calculate the determinate they show and then set it to zero and then
solve for 'f' and then simplify, but again it may not be easy because it's a 4x4.
When they say 'conveniently' they are not suggesting a simple solution to that determinant
i think what they really just mean is that it can be written that way which is much
simpler to write than other methods might be.
In many cases however we would leave the problem in matrix form and just use a matrix
solver to do the math when needed (when we dont need an analytical result).

As a side note, Lagrange's Interpolation Formula can be obtained by noting the pattern in that three point formula. In the numerators, there are terms (x-m) where m is one of the xi's, but with one of them missing (instead of all three xi's there are only two). In the other numerators, leave out a different xi and that forms the numerators. The denominators follow a slightly different but similar pattern.
So in other words the general term looks like:
Nn*fn/Dn
where Nn is the product of differences of x minus all the other xi's not including xn, and
where Dn is the product of differences xn minus all the other xi's not including xn, so
for a four point formula we would get:
(x-x2)(x-x3)(x-x4)*f1/((x1-x2)(x1-x3)(x1-x4))
for the first term, and
(x-x1)(x-x3)(x-x4)*f2/((x2-x1)(x2-x3)(x2-x4))
for the second term and the other terms in a similar manner.
This gets you right to the formula without all the linear algebra, and also you can use it for a larger number of points for interpolating other functions as well. There's a special version called the "Five Point Formula" that uses (yes) five points (instead of the three shown in this paper), but it is special because it is especially simple and includes 5 points which is pretty good for an interpolation formula.