Oct/Nov 2010

I think I just solved Question 1i.

A = Newton
B = Secant
C = Regular Falsi

I must go have another look.

The fastest one should be Newton (assuming Muller is not being used)

Then secant (which is pretty similar to Newton)

Then regula falsi (which is heading toward being a bisection method)..

So in size order of the tables that makes sense. I go look.

I hope the method is not that of substituting into the suspected formula and finding a match for the iterative x the table comes up with. Thought it may have to be that and fed the calculator some numbers that came back with x-next according to the table, using eg. the Newton equation for the suspected Newton table. I think if that is the case it's still a question to leave for last. All those long strings of numbers tend to hide my wrong button presses until it's much too late. Could take the entire two hours just feeding the relevant formulas.

Anyway it looks like a "feed the formula" experiment might be a way to solve the question. Hopefully you've worked out a short cut (although good on you for coming up with any solution).

What did you get for your first iteration of 1b?

I got:
delta-x₁ = -0.66617647
delta-x₂ = -0.134705882

I chickened out after the 2nd iteration of 1a.

So the solution is to feed the likeliest formula, and see what comes out?

For f' do you use divided differences?

Yes you need to use your intuition basically. Your other option is to spam. Do 2 iterations of each formula and match them up to the tables. Its not that hard.

For f' I used first year calculus

Have you looked at question 2a? what LU matrix do you get? Mine is identical to whats giving. Looks like a trick question?

3a is a spline

Also what matrix do you use for 3b? I used

6 15 55 152.6
15 55 198 2289
55 198 723 8393

I suppose practice would cut the time it consumed. It's a good solution. Actually a good question too. Requires thinking, whereas quite a lot of the others are just fitting a template.

And I suppose if one was to whinge about everything that threatens to consume a lot of time, then the real culprit to shout at would be the least squares matrix. 6X6 and ill conditioned is never going to be pretty.

Actually you know? Now the way is illuminated, a question like that for enough marks could be quite a welcome sight, couldn't it?

Of course if they do a dirty and invent new ways of making us think for this exam that'd be something else...

The second derivative also matches in 3a, so ja.

For 3b, For n degrees form an (n+1) by (n+1) M - matrix and solve. (This is an edit BTW).
So you have a (2+1) X (2+1), which is good for starters. You should have N in the upper corner.

I'll continue to edit my waffle. Just bypass it. It helps me to teach myself if I do this. Excellent! I hope we get a small degree least squares polynomial now. Was getting those badly wrong.

2a. The first question I have is "Do we have to 'unpivot' at the end?" That matrix requires 2 pivotings if you use normal Gaussian elimination to arrive at your LU, and one if you use scaled partial pivoting.

Just at a glance, (without pivoting), row 3 would have a factor of (-2/-1) in a₁₃, so even just on this one point it differs (since the factors don't get involved in the further manipulations).

Just in case I've got this backward, you subtract eg. a_ri/a_ii * Row-i from Row-r in the process of reducing column i. To make up LU you keep that factor (a_ri/a_ii) in the column, at the head of the row being operated on, and that factor will ultimately be in the "L" part of your LU. Even if A reduces to A, LU should differ.

I can't recall A reducing to A in that exam, but then would I?

I'll go do it and report back.

Less rambling more action.

sum Y_i * sum x_i <> x₁Y₁ + x₂Y₂ + x₃Y₃.

(3b. )

eg. try Y₁ * x₁.

In other words vector b needs recalc. b₂ is wrong. It should be 585.6

For M₂₃ I get 1 + 8 + 27 + 64 + 125 = 225

For M₃₃ I get 1 + 16 + 81 + 256 + 625 = 979

2a. i. Pivoting or not pivoting?

ii. Why? (or Why not?)

iii. What effect does that have on outcome?
Specifically: Do we have to rearrange anything?

If you scale it you get:
1........ -2 ..... -1 <-------------------- may as well switch sign while about it.
0........ 1 ...... 0.75
-0.4.... 0 ..... 1

«Rats! This "scaling" is wrong! 2 is the largest value in row 1, whatever you do»

Note that no pivoting is required in this case. The 1 in col 1 is now the greatest there. 1 > 2

Another thing. I think it may be significant that they ask for "an LU factorisation". Any of these might do?

Reduce col 1.
1........ -2 ..... -1
(0)...... 1 ...... 0.75
(-0.4).. 0.. ....0.6

Reduce col 2.
1........ -2 ..... -1
(0)...... 1 ...... 0.75
(-0.4).. (0).....0.6

For a moment I thought I'd reduced A back to A, and maybe you've made a similar mistake. Remember, though:

All those parenthed values represent Zero.

Knowing that there's a zero there just gives a convenient pigeonhole for storing the multiplier that made it so. U is then an upper triangular matrix with the zeros in their places; L is a lower triangular matrix with the values in parenthesis now taken as values, and with 1's down the main diagonal.

I made a horrible mess of this several times, but I think it's OK now. Nice to be able to edit on Phorum.

Just leaving the values as is and pivoting I end up with:

-2 ....... 0 ......... 5
(0) ...... 8 ......... 6
(0.5).. (0.25) .. -3

This also gives an LU decomposition of A?

===
Carrying on as if it does.

y = [0 10 8.5]^T by simple forward substitution.

and then y = b' = Ux gives

[7.0833 -6.9998 2.8333]^T

Recap: Ax = LUx = Ly = b => y = b' = Ux from which solve for x.

Hmm...Let me play with 2a a bit. I think my brain was a bit messed up when I looked at it.

Also, I think my matrix for 1b was wrong. My partial derivatives were incorrect and threw my calculations out the window. My matrix to solve should be:

My solution for 1b is the matrix:
6.5 1.5 -2.5
36.75 32.5 -1.625

Which you can then solve for and get
delta-x1 = 0.504803843
delta-x2 = 0.520816653

My matrix for 2a:

1 -2 -1
(0) 8 6
(-2) (0.5) 1

I think its wrong because I did nothing with row 2 and just put the zero in brackets to show nothing needed doing there....

I think I may have this backwards, but the least squares polynomial I end up with is:

-16.468 + 25.6905 x + 2.4369 x²

How does that compare? (I hope I was doing something wrong in the sense of doing too much work, because it took ages).

Will have to check my exercise book in the am. Did you use the matrix method to do the calc?

Somehow missed those replies first time round.
======================================

2a. OK we've both subtracted 0 times row 1 in the LU matrix (done zilch), and then your factor for row 3 is -2, whereas mine is 0.5. Row 3 solutions are basically the same except that they're inverses.

I use the template THIS - THIS / THAT * THAT.

The THATs cancel. That leaves THIS - THIS = 0.

So the "head of the column to be reduced" must be the denominator.
The pivot element for this reduction must be the numerator.

Looking at the original matrix (pivoted, I think), "THIS" would be -1 after the pivot, and on the diagonal would be -2. This over that = 1/2 then. Which is no big deal, really.
========================================

The solution for the least squares I got by struggling along very slowly through the matrix solution, yes. If there's an easier way I want to sign up right away.

I set up the matrix with the sums as required, pivoted, got the first awkward multiplier, hopefully subtracted row 1 from row k instead of the other way round ... etc etc... No insight to offer, just plod.

=========================================

I keep forgetting 1b. You can probably ignore the remainder of the post if you like. I just need to fire up the memory and see if there's anything left in there of yesterday's work on "Newton Systems"...

-f = f_x dx + f_y dy
-g = g_x dx + g_y dy

Notation's not quite right, but it's clear what I mean. No problem there, I don't think.

And no need to go back over why it actually is Newton's method by other means ...

Right. So one gets initial values from say a graph. x₀, y₀.

One makes up a table of the partial derivatives (all four) and restates the functions given in the "= 0" form. So with the seed values f can give us an f₀, g can give us a g₀ and all the partial derivatives can give us plugin values too.

With all that plugged in we have a matrix (alternatively just equations where you use one to state eg. y in terms of x, and substitute). ... That's it, right? Oh. And your "x" vector has delta-x, delta-y in it.

----
I'll shut up for a few minutes now...