Differential Calculus 201-SN2-RE • CEGEP, Montreal

Revision sheet: bisection, Newton's method and fixed-point iteration (201-SN2-RE)

Q: How many bisection iterations are needed to get four decimals?

Solve the length of the interval divided by two to the power n, less than ten to the power minus four. Starting from an interval of length one, you need at least fourteen iterations. The general rule is about three point three two iterations per extra decimal place, because bisection divides the error by two and not by ten.

Q: Why does Newton's method not always converge?

Because its convergence is local: it is guaranteed only near a simple root. Far from the root, the tangent line can send you anywhere. Three classic failures exist: a zero derivative that makes the division impossible, a cycle between two values, and plain divergence. The remedy is to locate the root by bisection first.

Q: How do you know whether the rewrite x equals g of x will converge?

Compute the derivative of g near the fixed point. If its absolute value is strictly less than one, the sequence converges; if it is greater than one, it diverges. The sign gives the shape: a positive derivative converges as a staircase, a negative derivative as a spiral. This criterion is checked before iterating, not after.

Q: When should you stop iterating?

When two successive iterates agree to the required decimals, and only after certifying the result with a bracket. A criterion based on the value of f alone is misleading: on a very flat function, f can be tiny quite far from the root. So you must measure the horizontal distance, not the height.

Q: Why does Newton's method become slow on some equations?

Because the root is multiple, that is, the function and its derivative both vanish there. Convergence is then no longer quadratic but linear, and the number of correct decimals grows by a fixed amount per step, often less than one, instead of doubling. The speed comes back if you multiply the correction by the multiplicity of the root.

The computation in this chapter is easy: a formula, a calculator, four rows of a table. What costs marks is around it: justifying that the root exists, choosing the starting point, and the sentence that says how accurate your answer is.

This sheet is written for CEGEP students in the Science program (Sciences de la nature) taking Differential Calculus, 201-SN2-RE (formerly 201-NYA). Once the sheet is read, the corrected exercise set on the same chapter puts every reflex to the test.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

The thread of the chapter

A numerical method never gives the root, it gives a SEQUENCE that approaches it: so you must always say how close you got, and why the sequence converges. Marks are lost on those two sentences, not on the computation.

This chapter is part of 201-SN2-RE, Differential Calculus

The essentials

Bisection: slow, but it never misses

• Hypothesis: $f$ continuous on $[a, b]$ with $f(a)f(b)<0$ . Cut in half and keep the half where the sign changes.
• Width of the bracket after $n$ steps: $\frac{b-a}{2^{n}}$ . It is a GUARANTEE, not an estimate.
• LINEAR convergence with ratio $\frac{1}{2}$ : about $3.32$ iterations per extra decimal place, since $\log_{2}10\approx 3.32$ .
• It needs neither a derivative nor a good starting point, and it gives a certified BRACKET, which no other method of the chapter provides.

x^{3}+x-1

, each step keeps the half where the sign changes:

[0, 1]

[0.5, 1]

[0.5, 0.75]

[0.625, 0.75]

. The width is halved every time.

To get $p$ decimals on $[a, b]$ , solve $\frac{b-a}{2^{n}}<10^{-p}$ , which gives $n>\frac{\ln\frac{b-a}{10^{-p}}}{\ln 2}$ . This inequality is the most frequent theory question of the chapter.

Newton's method: the tangent line instead of the curve

• $x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}$ , obtained by solving the equation of the tangent line at the point $\left(x_{n}, f(x_{n})\right)$ .
• QUADRATIC convergence near a SIMPLE root: the number of correct decimals doubles at every step, with $e_{n+1}\approx\frac{f''(r)}{2f'(r)}e_{n}^{2}$ .
• It requires $f'$ , a starting point close enough, and $f'(x_{n})\neq 0$ at every step.
• No global guarantee: Newton's method can cycle, diverge, or converge only linearly.

Newton's method replaces the curve by its TANGENT LINE at

x_{0}=3

: it crosses the axis at

x_{1}\approx 1.83

, much closer to

\sqrt{2}

. The price to pay is that

f'

must be known.

The four ways Newton's method fails

• 1. $f'(x_{n})=0$ : the tangent line is horizontal, the division is impossible and the iteration stops dead.
• 2. A CYCLE between two values, as on $x^{3}-2x+2$ starting from $0$ , where the sequence goes $0$ , $1$ , $0$ , $1$ forever.
• 3. DIVERGENCE, as on $x^{1/3}$ where the iteration gives $x_{n+1}=-2x_{n}$ and moves away from the root at every step.
• 4. Convergence that is only LINEAR at a multiple root, where $f$ and $f'$ vanish together.

x^{1/3}

, each tangent line sends you twice as far, on the other side:

1

, then

-2

, then

4

. The sequence

x_{n+1}=-2x_{n}

moves away from the root

0

The usual remedy is the hybrid: a few bisection steps to get closer, then Newton's method to finish fast. That is what real numerical libraries do.

Secant method and fixed-point iteration, and the three iterations to know

• SECANT METHOD: $x_{n+1}=x_{n}-f(x_{n})\frac{x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}$ , the tangent line replaced by the secant line through the last two points. Order $\varphi\approx 1.618$ , but only ONE evaluation per step.
• FIXED-POINT ITERATION: rewrite $f(x)=0$ as $x=g(x)$ and iterate $x_{n+1}=g(x_{n})$ . Convergence if $\left|g'(r)\right|<1$ nearby, as a STAIRCASE if $g'>0$ , as a SPIRAL if $g'<0$ .
• Newton's method is the special case of fixed-point iteration where $g'(r)=0$ , which explains its speed.
• Three useful iterations: $\sqrt{a}$ by $x_{n+1}=\frac{1}{2}\left(x_{n}+\frac{a}{x_{n}}\right)$ , $\frac{1}{a}$ without division by $x_{n+1}=x_{n}(2-ax_{n})$ , and $\sqrt[3]{a}$ by $x_{n+1}=\frac{1}{3}\left(2x_{n}+\frac{a}{x_{n}^{2}}\right)$ .

x_{n+1}=\cos x_{n}

: since

g'=-\sin x<0

near the fixed point, the sequence turns around it in a SPIRAL;

|g'|<1

, so the spiral tightens.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Running Newton's method without looking at the derivative at the starting point

the whole question

What not to write

“ $x_{0}=0$ for $f(x)=x^{2}-4$ : $x_{1}=0-\frac{-4}{0}$ ...”

What to write

“ $f'(0)=0$ : Newton's method is undefined at this point, so change $x_{0}$ , for example $x_{0}=3$ .”

x_{0}=0

, the tangent line to

x^{2}-4

is horizontal (red): it never crosses the axis, and the formula divides by

f'(0)=0

. Start again from a point where the slope is not zero.

Why: A horizontal tangent line never crosses the axis. Looking at the sign of $f'$ on the starting interval takes five seconds and avoids an impossible computation.

2. Assuming Newton's method converges because it usually does

2 marks, and a wrong conclusion on a whole problem

What not to write

“Newton's method always converges to the root, it is quadratic.”

What to write

“Newton's method converges quadratically NEAR a simple root. On $x^{3}-2x+2$ starting from $0$ , the sequence goes $0$ , $1$ , $0$ , $1$ and does not converge.”

Starting from

x_{0}=0

, Newton's method sends you to

x_{1}=1

, whose tangent line sends you back to

0

: the sequence cycles forever and never approaches the root, which lies near

-1.77

Why: The convergence of Newton's method is LOCAL: it is a property of the neighbourhood of the root, not of the method. A badly chosen starting point is enough to break everything.

3. Confusing the number of iterations with the number of decimals

2 marks, and a false accuracy announced

What not to write

“After $10$ bisection iterations, I have $10$ correct decimals.”

What to write

“After $10$ iterations on $[0, 1]$ , the bracket has width $\frac{1}{2^{10}}\approx 10^{-3}$ : three decimals, not ten. It takes about $3.32$ per decimal place.”

Why: Bisection divides the error by $2$ , not by $10$ . The conversion factor is $\log_{2}10\approx 3.32$ , and it is the one number to remember from the chapter.

4. Rewriting $f(x)=0$ as $x=g(x)$ without looking at $g'$

the whole question, and a table of values that runs off to infinity

What not to write

“ $x^{2}-x-2=0$ can be rewritten $x=x^{2}-2$ , and I iterate from $x_{0}=1.9$ .”

What to write

“At the fixed point $r=2$ , $g'(2)=4$ and $\left|g'\right|>1$ : the sequence DIVERGES. The rewrite $x=\sqrt{x+2}$ gives $g'(2)=\frac{1}{4}$ and converges.”

Same equation, two rewrites: starting from

1.9

, the sequence

x_{n+1}=x_{n}^{2}-2

(red) moves away from

2

, where

|g'(2)|=4

; the sequence

x_{n+1}=\sqrt{x_{n}+2}

(green) closes in on it,

|g'(2)|=\frac{1}{4}

Why: A single equation has infinitely many rewrites and only some of them converge. The criterion $\left|g'(r)\right|<1$ is checked BEFORE iterating, otherwise you discover the failure after six lines of computation.

5. Cutting an interval where the sign does not change

the whole question

What not to write

“ $f(0)=1$ and $f(2)=3$ , I cut at $1$ and carry on with the bisection.”

What to write

“ $f(0)f(2)>0$ : bisection does not apply. There may be no root on $[0, 2]$ , or else an EVEN number of roots.”

f(0)

and

f(2)

are both positive, and yet

f

vanishes twice between them. Without a sign change at the endpoints, bisection has nothing to cut.

Why: The sign change is the hypothesis that makes the method work, through the Intermediate Value Theorem. Without it, the half you keep may contain no root at all.

6. Stopping the iterations on the value of $f$ alone

1 to 2 marks, and an accuracy announced without proof

What not to write

“ $\left|f(x_{5})\right|<10^{-6}$ , so $x_{5}$ approximates the root to within $10^{-6}$ .”

What to write

“A small $\left|f(x_{5})\right|$ guarantees nothing if $f$ is FLAT: you need a bracket, or the criterion $\left|x_{n+1}-x_{n}\right|<\varepsilon$ , and preferably both.”

Why: On $f(x)=(x-1)^{5}$ , the value $f(1.1)$ is $10^{-5}$ while the error on the root is $0.1$ . A criterion on $f$ alone measures the height, not the horizontal distance.

7. Not suspecting a multiple root when convergence is slow

1 to 2 marks, and a lot of time

What not to write

“Newton's method takes twenty iterations, my calculator must be inaccurate.”

What to write

“ $f$ and $f'$ vanish together: the root is MULTIPLE and Newton's method is only linear there. The lost factor is recovered with $x_{n+1}=x_{n}-m\frac{f(x_{n})}{f'(x_{n})}$ , where $m$ is the multiplicity.”

Why: Doubling the decimals is the hallmark of a simple root. When it does not happen, that is a diagnosis, not a calculator failure.

8. Rounding the iterates along the way

1 to 2 marks, and the convergence you claim can no longer be checked

What not to write

“I round $x_{n}$ to three decimals at every step to keep the table light.”

What to write

“Keep every decimal the calculator gives from one step to the next, and round ONLY the final answer.”

Why: Newton's method doubles the correct decimals at every step: rounding to three decimals caps the accuracy at three decimals for good, and the method loses exactly what makes it valuable.

Which method to choose

Which method, depending on what you have

The choice is not a matter of taste but of three pieces of data: do you have $f'$ , do you have a good starting point, and does the question ask for a guarantee or for speed.

If the question asks for a certified BRACKET, or says “with certainty” → bisection, the only method that guarantees its accuracy at every step

Example: $\frac{b-a}{2^{n}}<10^{-4}$ fixes the number of steps in advance
If $f'$ is easy to write and you have a nearby starting point → Newton's method, for its quadratic convergence

Example: $x^{3}+x-1=0$ starting from $x_{0}=1$ gives eight decimals in four steps
If $f'$ is complicated, unknown, or expensive to evaluate → the secant method, which replaces the tangent line by the secant line

Example: order $\varphi\approx 1.618$ but a single evaluation per step

At equal cost the secant method often beats Newton's method, since $\varphi^{2}\approx 2.618>2$ : two secant steps are worth more than one Newton step.
If the equation is already given in the form $x=g(x)$ → fixed-point iteration, AFTER checking $\left|g'\right|<1$ near the root

Example: $x=\cos x$ converges in a spiral to $0.739$
If $f$ and $f'$ vanish at the same point → multiple root: bisection, or Newton's method modified by the factor $m$

Example: $(x-1)^{3}$ at $x=1$
If you know nothing at all about where the root is → hybrid: a few bisection steps to locate it, then Newton's method to finish

Example: this is what real numerical libraries do

Before any method, you must have shown that the root EXISTS and located it. The Intermediate Value Theorem does that job, and forgetting it costs more than choosing the wrong method.

What to do when the sequence does not converge

A sequence that does not converge is a diagnosis to make, not a breakdown. Three symptoms, three causes.

If the division is impossible at some step → $f'(x_{n})=0$ : change the starting point, or do a bisection first

Example: $x_{0}=0$ on $f(x)=x^{2}-4$
If the sequence keeps coming back to the same values → a cycle: change $x_{0}$ , there is nothing else to do

Example: $0$ , $1$ , $0$ , $1$ on $x^{3}-2x+2$
If the values grow step after step → divergence: the starting point is outside the basin of attraction, get closer by bisection

Example: $x^{1/3}$ , where $x_{n+1}=-2x_{n}$
If the sequence converges but only gains decimals at a slow, steady rate → a multiple root, or a fixed point with $\left|g'\right|$ close to $1$ : diagnose before insisting

Example: twenty steps for four decimals on $(x-1)^{3}$

In every case, WRITE the diagnosis on your test. “The sequence cycles, so I change the starting point” earns marks; a table abandoned halfway earns none.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Locate a root before approximating it

When to use it: Every numerical solving question starts there, even when the question does not explicitly ask for it.

1 Name the function: “Let $f(x)=x^{3}+x-1$ , defined on $\mathbb{R}$ .”
2 Justify continuity by its REASON: “ $f$ is a polynomial, so it is continuous on $\mathbb{R}$ .”
3 Find a sign change and write it down: “ $f(0)=-1<0$ and $f(1)=1>0$ .”
4 Conclude existence by the Intermediate Value Theorem, then uniqueness by strict monotonicity: “ $f'(x)=3x^{2}+1>0$ , so $f$ is strictly increasing.”
5 Only then announce the method chosen and the starting point.

Concluding sentence

Since $f$ is continuous and strictly increasing on $[0, 1]$ with $f(0)<0<f(1)$ , the equation $f(x)=0$ has a unique solution $r$ in $\left(0, 1\right)$ .

The trap: Jumping straight into the computation and taking the root for granted. The table of iterations may be perfect, it is worth nothing until the existence of the limit has been established.

Marking: Usually 1 mark for the justified continuity, 1 mark for the sign change, 1 mark for uniqueness by monotonicity.

Write up a Newton iteration with its accuracy check

When to use it: The question asks for an approximate value to within $10^{-p}$ using Newton's method.

1 Write the iteration formula EXPLICITLY, with the $f$ of the question: “ $x_{n+1}=x_{n}-\frac{x_{n}^{3}+x_{n}-1}{3x_{n}^{2}+1}$ .”
2 Announce the starting point and justify it: “Take $x_{0}=1$ , which lies in the interval where the root was located.”
3 Present the iterates in a table, with every decimal the calculator gives, without rounding along the way.
4 Stop when two successive iterates agree to the required decimals, and SAY so: “ $x_{3}$ and $x_{4}$ agree to the sixth decimal.”
5 Certify by a sign change: “ $f(0.68232)<0<f(0.68233)$ , so $0.68232<r<0.68233$ .”

Concluding sentence

Newton's method gives $r\approx 0.682328$ , and the bracket $f(0.68232)<0<f(0.68233)$ certifies this value to within $10^{-5}$ .

The trap: Announcing the accuracy from the number of decimals shown by the calculator. Only a bracket from a sign change, or an error bound, proves anything.

Marking: 1 mark for the explicit formula, 1 mark for the table of iterates, 1 mark for the stated stopping criterion, 1 mark for certification by a bracket.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

Substitute the value found back into the original equation

Compute $f$ at the approximate value: the result must be very small, and above all of the right order of magnitude compared with the accuracy claimed.

$f(0.682328)\approx 5\times 10^{-7}$ for $f(x)=x^{3}+x-1$ : consistent with six decimals. A result of $0.03$ would say that the table contains a typo.
Certify by a sign change, never by the display

Evaluate $f$ at both endpoints of the bracket you claim and check that they have opposite signs. It is the only acceptable proof of accuracy.

$f(0.68232)<0$ and $f(0.68233)>0$ prove $0.68232<r<0.68233$ . The eight decimals shown by the calculator prove nothing.
Count the decimals that stabilize from one step to the next

With Newton's method at a simple root, this number should roughly DOUBLE at every step. If it only grows by a fixed amount, often less than one decimal per step, the root is probably multiple.

$0.75$ , then $0.686$ , then $0.68234$ , then $0.6823278$ : two, four then seven decimals, the doubling is visible.
Check RADIAN mode in any trigonometric equation

The derivatives used by Newton's method assume the argument is in radians. A quick check: $\cos 1$ must display $0.5403$ , and not $0.9998$ .

The equation $x=\cos x$ has the solution $0.739$ in radians and $0.9998$ in degrees: both numbers look plausible, only the mode tells them apart.

The typical problem, taken apart

Solving $x^{3}+x-1=0$ by Newton's method, with certification

Consider the equation $x^{3}+x-1=0$ .

1. Show that it has a unique real solution and locate it.

2. Give an approximate value of it to within $10^{-5}$ by Newton's method, then certify the result.

Step 1

$f(x)=x^{3}+x-1$ is a polynomial, so it is continuous on $\mathbb{R}$ . $f(0)=-1<0$ and $f(1)=1>0$ , so by the Intermediate Value Theorem there exists $r\in\left(0, 1\right)$ such that $f(r)=0$ .

Why

This line earns the first mark and makes the rest legitimate: without it, the table of iterations approximates a limit that nothing says exists.

Step 2

$f'(x)=3x^{2}+1>0$ for every $x$ , so $f$ is strictly increasing on $\mathbb{R}$ : the solution $r$ is UNIQUE.

Why

Uniqueness is a second sentence, with a second argument. The Intermediate Value Theorem never gave it, and confusing it with existence costs a mark on every test.

Step 3

Newton's formula here reads $x_{n+1}=x_{n}-\dfrac{x_{n}^{3}+x_{n}-1}{3x_{n}^{2}+1}$ , with $x_{0}=1$ , chosen in the interval located.

Why

Write the EXPANDED formula with the $f$ of the question, not the general formula. That is what proves the derivative was computed, and it avoids copying errors at the next step.

Step 4

$x_{1}=1-\dfrac{1}{4}=0.75$ ; $x_{2}=0.686046\ldots$ ; $x_{3}=0.682339\ldots$ ; $x_{4}=0.6823278\ldots$

Why

Keep every decimal from one step to the next. Rounding here would cap the accuracy and lose exactly what Newton's method brings, namely the doubling of correct decimals.

Step 5

$x_{3}$ and $x_{4}$ agree to the fifth decimal: keep $r\approx 0.68233$ , that is $0.682328$ to within $10^{-6}$ .

Why

The stopping criterion is announced, not guessed. Two iterates that agree to $p$ decimals is the usual criterion, and here it is justified by quadratic convergence.

Step 6

Certification: $f(0.68232)\approx-1.9\times 10^{-5}<0$ and $f(0.68233)\approx 5.3\times 10^{-6}>0$ , so $0.68232<r<0.68233$ .

Why

It is the only acceptable proof of the accuracy claimed. A sign change brackets the root with certainty, whereas the calculator display certifies nothing at all.

Step 7

Comparison: for the same bracket of width $10^{-5}$ starting from $[0, 1]$ , bisection would need $n$ such that $\dfrac{1}{2^{n}}<10^{-5}$ , that is $n\geq 17$ iterations against $4$ .

Why

This computation is often the last question of the exercise, and it takes one line with $\log_{2}$ . It puts a number on the advantage of Newton's method, which only holds because the root is simple.

The conclusion, written out

The equation $x^{3}+x-1=0$ has a unique real solution $r$ , and Newton's method starting from $x_{0}=1$ gives $r\approx 0.68233$ , a value certified by the bracket $0.68232<r<0.68233$ .

The classic mistake on this problem: Stopping at $x_{2}=0.686$ and announcing three correct decimals, because three decimals are displayed. But $x_{3}=0.68234$ : the third decimal had not yet stabilized, and only comparing two successive iterates, or a sign change, can tell you so.

Learn by heart

• Bisection: width $\frac{b-a}{2^{n}}$ after $n$ steps, about $3.32$ iterations per decimal place.
• Bisection: you NEED $f(a)f(b)<0$ , otherwise the method says nothing.
• Newton: $x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}$ , quadratic only near a SIMPLE root.
• The four failures of Newton's method: $f'=0$ , cycle, divergence, multiple root.
• Fixed point: the sequence $x_{n+1}=g(x_{n})$ converges if $\left|g'(r)\right|<1$ , and this criterion is checked BEFORE iterating.
• Secant: order $\varphi\approx 1.618$ , a single evaluation per step, often more efficient than Newton's method at equal cost.
• No accuracy is announced without proof: a bracket from a sign change, or nothing.
• Round only at the very end: rounding along the way caps the accuracy.

Frequently asked questions

How many bisection iterations are needed to get four decimals?

Solve the length of the interval divided by two to the power n, less than ten to the power minus four. Starting from an interval of length one, you need at least fourteen iterations. The general rule is about three point three two iterations per extra decimal place, because bisection divides the error by two and not by ten.

Why does Newton's method not always converge?

Because its convergence is local: it is guaranteed only near a simple root. Far from the root, the tangent line can send you anywhere. Three classic failures exist: a zero derivative that makes the division impossible, a cycle between two values, and plain divergence. The remedy is to locate the root by bisection first.

How do you know whether the rewrite x equals g of x will converge?

Compute the derivative of g near the fixed point. If its absolute value is strictly less than one, the sequence converges; if it is greater than one, it diverges. The sign gives the shape: a positive derivative converges as a staircase, a negative derivative as a spiral. This criterion is checked before iterating, not after.

When should you stop iterating?

When two successive iterates agree to the required decimals, and only after certifying the result with a bracket. A criterion based on the value of f alone is misleading: on a very flat function, f can be tiny quite far from the root. So you must measure the horizontal distance, not the height.

Why does Newton's method become slow on some equations?

Because the root is multiple, that is, the function and its derivative both vanish there. Convergence is then no longer quadratic but linear, and the number of correct decimals grows by a fixed amount per step, often less than one, instead of doubling. The speed comes back if you multiply the correction by the multiplicity of the root.

Practise it

Corrected exercises: Bisection, Newton's method and fixed-point iteration, 201-SN2-RE

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

16 corrected exercises
160 points
225 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Rolle's theorem and the mean value theorem Next sheet L'Hôpital's rule and indeterminate forms

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-calc1-numerical-methods. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Looking for a 201-SN2-RE tutor in Montreal?

Get in touch for a first session. We work on solving equations numerically at the level of real CEGEP tests, from the bisection method all the way to the quadratic convergence of Newton's method.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: bisection, Newton's method and fixed-point iteration (201-SN2-RE)

The essentials

Bisection: slow, but it never misses

Newton's method: the tangent line instead of the curve

The four ways Newton's method fails

Secant method and fixed-point iteration, and the three iterations to know

The mistakes that cost marks

1. Running Newton's method without looking at the derivative at the starting point

2. Assuming Newton's method converges because it usually does

3. Confusing the number of iterations with the number of decimals

4. Rewriting f(x)=0f(x)=0f(x)=0 as x=g(x)x=g(x)x=g(x) without looking at g′g'g′

5. Cutting an interval where the sign does not change

6. Stopping the iterations on the value of fff alone

7. Not suspecting a multiple root when convergence is slow

8. Rounding the iterates along the way

Which method to choose

Which method, depending on what you have

What to do when the sequence does not converge

How the answer is expected to be written

Locate a root before approximating it

Write up a Newton iteration with its accuracy check

Check before you hand in

The typical problem, taken apart

Solving x3+x−1=0x^{3}+x-1=0x3+x−1=0 by Newton's method, with certification

Learn by heart

Frequently asked questions

How many bisection iterations are needed to get four decimals?

Why does Newton's method not always converge?

How do you know whether the rewrite x equals g of x will converge?

When should you stop iterating?

Why does Newton's method become slow on some equations?

Corrected exercises: Bisection, Newton's method and fixed-point iteration, 201-SN2-RE

See also

Looking for a 201-SN2-RE tutor in Montreal?

4. Rewriting $f(x)=0$ as $x=g(x)$ without looking at $g'$

6. Stopping the iterations on the value of $f$ alone

Solving $x^{3}+x-1=0$ by Newton's method, with certification