这是国外要求学生对多次方程求解进行研究所布置的作业,要求用电脑完成

U6 P2 Coursework – Numerical Methods

General Points

1. A Numerical method should not be used when an analytical one is available
2. There are 2 parts to a numerical method

a.         Estimation of the answer

b.         Establishing error bounds

3.   An answer derived using a numerical method and without any reference to its level of accuracy is of no value

4.   It is not acceptable to determine error by referring to a known, correct answer

5.   A general equation is represented by f(x) = 0

6.   The roots of this are the x-values of the points where the curve y = f(x) cuts the x-axis

Coursework Requirements

Candidates must use the following 3 methods

1. Search for a sign change using the bisection method
2. Fixed point iteration using the Newton-Raphson method
3. Fixed point iteration by rearranging the equation f(x) = 0 into the form x = g(x)

A different equation must be used for each method

Candidates must explain how they chose each equation

Bisection Method

1.      It is sufficient to find one root only (show that a sign change does exist first)

2.      The method must also be shown failing

Failure means:

·        Not finding all the roots

·        Finding a root other than expected

·        Finding a false root

3.   The process must be shown graphically

4.   Diagrams should be easy to follow – add on extra labels to Autograph diagram

5.   Only a few steps need to be shown

6.   Error or solution bounds should be established for at least one root

      They should be given numerically as:

                  i.          error bounds e.g. 2.614 ± 0.0005

                  ii.          solution bounds 2.6135 < x < 2.6145

7. Roots should be found to at least 3 decimal places of accuracy

Comparison of Methods

1. Discuss ease of use
2. Discuss speed of convergence

In order to do this you need to find one root of one of your equations by all 3 methods (Do at the end of the project)

Method

1. You must understand what is happening graphically
2. You should draw a sketch and include it in your write up. The sketch should be annotated to show how the method works
3. Explain what is going on. e.g. if f(c)>0 then the root is in the interval [2,c], if f(c)<0 then the root is in the interval [c,3]
4. Explain how the spreadsheet works and add in an additional formula table to show how the different cells were worked out

Advantages of Bisection Method

1. Reasonably safe
2. Every estimate of the root has solution bounds built in. [the end points of the smallest interval in which it lies]

Disadvantages of Bisection Method

1. More steps to achieve a given level of accuracy. Not too bad when using the spreadsheet (it is very slow!!)
2. One or more root may be missed if several roots are very close together

Some do’s and don’ts

• You must state any formulae used in constructing a spreadsheet
• Don’t produce endless print outs unless they show what is actually happening
• You need to know how to program the necessary decision making

e.g. IF(D4<0,C4,A4) or use the conditional statements built into Excel

 Newton-Raphson Method

The equation f(x)=0 is solved using the iteration:

Roots should be found to at least 5 significant figures

If the result for the root is 2.5387 (5.s.f.) then the root lies in the range

2.53865 < root < 2.53875

To be safe, it is necessary to evaluate f(x) at both these points and show that one value is positive and the other is negative (sign change)

Method

• Describe how the method works – use of tangents etc
• Show using Autograph how to find one root but find all roots using a spreadsheet
• Explain how the cells in the spreadsheet were obtained
• Establish error bounds for one of the roots
• Show how the method may not work. e.g. at turning points

Advantages of Newton-Raphson

·        This method usually produces convergence and is normally fairly quick as long as the starting point is close to the required root.

Disadvantages of Newton-Raphson

·        Difficult to use when carrying out the iterations with a calculator

·        To use this method you must be able to differentiate the required function

·        In some cases it is not sufficient to start with an end point of the unit interval containing the root

Fixed Point Iteration

This involves finding a single value or point of an estimate for the value of x, rather than establishing an interval within which it must lie.

A root of an equation is determined by finding a sequence of estimates and looking at the pattern of convergence

Any equation f(x) = 0 can be rearranged in the form x = g(x) in any number of ways of which can be used as a basis for the iteration:

The iteration in this process is represented graphically as either a ‘staircase’ or a ‘cobweb’ diagram.

Method

1. Choose a value of x
2. Take a starting point on the x-axis
3. Find the corresponding value of y
4. Move vertically to the curve
5. Make value of y into new value of x
6. Move to line y = x
7. Find the corresponding value of y
8. Move vertically to the curve

Etc

NOTE:

• Choose a new equation and find one root
• Show using Autograph mentioning the ‘staircase’ and ‘cobweb’ convergence
• If it clearly does converge then use a spreadsheet to find the root again explaining what is going on and how the cell values are obtained
• If it doesn’t converge then you must discuss the gradient. (if it does converge then an example must be used later on when it doesn’t converge by using a different rearrangement)
• Solutions must be found to at least 5 significant figures

Convergence

The iteration will converge if:

1.         The starting value is suitable

2.         The gradient of the curve at the point of intersection is between –1 and 1. If the gradient of g(x) is negative the convergence / divergence is less easy to see

Disadvantages of Fixed Point Iteration

• If the equation has more than 1 root, and f(x) is continuous then this method may miss one or more roots
• There can be hit or miss when trying to rearrange to make x the subject as not all rearrangements will work
• Needs decent algebra to rearrange in the form x = ….

Comparison of the Methods

q       Use one of the equations you have previously used and find the same root using the other 2 methods (on a spreadsheet but there is no need to say what you are doing)

q       Compare speed of convergence and ease of use

q       Discuss use of available software and how easy the 3 methods are to use with Autograph and Excel. e.g. how easy is it to use the formulae in Excel.