How do you find the margin of error in Newton's method? (1 Viewer)

pomsky · Oct 4, 2015

Newton's method is used to find an approximation to the positive root $x=\sqrt{c}$ of the equation $x^2-c=0.$ The initial approximation is $x=a $(for some a>0).$$ The error in this initial approximation is $e_0 = |a-\sqrt{c}|.$ Show that the error $e_1$ in the next approximation (obtained by one application of Newton's method) is given by $e_1 = \frac{{e_0}^2}{2a}.$

Any advice on how to approach this?

rand_althor · Oct 4, 2015

pomsky · Oct 4, 2015

rand_althor said:
$$Use $x_1=x_{0}-\frac{f(x_0)}{f'(x_0)}$, where $x_{0}=a$, to find the second approximation. The margin of error between this appromixate root $x_1$ and the actual root $\sqrt{c}$ is given by the distance between them, i.e. $\left |x_1-\sqrt{c} \right |$. Simplify this to get the required expression.$

Thanks Rand

Few questions: What is f(x)? Is it x=sqrt (a)? Because if so, what's f'(x)? Is that dx/dc or dc/dx?

rand_althor · Oct 4, 2015

f(x) is the expression they've stated, x² - c. f'(x) would be 2x, as c is a constant.

pomsky · Oct 4, 2015

Sweet- thanks Rand

Mind if you help me solve another Q? Dunno how to get rid of coefficients in binomial: "The real number x is a solution of the equation $x^2 -x -1 =0$ . Use the binomial theorem to show that the sum $S$ of the series $1+ x+ x^2 +...+x^{2n-1}$ , where $n$ is an integer $\geq 1$ , is given by $S = \sum\limits_{r=1}^n ^nC_r x^{r+1}$

InteGrand · Oct 4, 2015

pomsky said:
Sweet- thanks Rand

Mind if you help me solve another Q? Dunno how to get rid of coefficients in binomial: "The real number x is a solution of the equation $x^2 -x -1 =0$ . Use the binomial theorem to show that the sum $S$ of the series $1+ x+ x^2 +...+x^{2n-1}$ , where $n$ is an integer $\geq 1$ , is given by $S = \sum\limits_{r=1}^n ^nC_r x^{r+1}$

$Note that $x$ isn't an arbitrary variable here, rather, it refers to a number that satisfies $x^2 - x - 1 = 0$ (there are two such $x$, but it is unnecessary to find what they are). From this equation, we know that $x^2 = x+1$ and $x(x-1) = x^2 -x = 1$ (we will use these facts) later. Let the series be $S_1 = 1 + x + x^2 + \cdots + x^{2n-1}$. Note that clearly $x\neq 1$, so by the sum of a geometric series formula, we have $S_1 = \frac{x^{2n}-1}{x-1}\Rightarrow (x-1)S_1 = x^{2n}-1$ (note that this geometric series formula is not valid if the common ratio is 1, which is why we made clear that $x$, the common ratio, is not 1 (it can't be 1 because 1 does not satisfy the equation that $x$ satisfies)). We have$

$$S=\sum_{r=1}^n \binom{n}{r}x^{r+1}=x\left(\sum_{r=1}^n \binom{n}{r}x^{r}\right)$ (factoring out one $x$)$

$$=x\left(\sum_{r=0}^n \binom{n}{r}x^{r} -1\right)$ (starting the sum from $r=0$ and subtracting 1 to compensate, since putting in the $r=0$ term means we have added 1 to the series, because the $r=0$ term is 1)$

$$=x\left((1+x)^n -1\right)$ (binomial theorem)$

$$=x\left((x^2)^n -1\right)$ (as we are given that $1+x = x^2$)$

$$=x\left(x^{2n}-1\right)$ (index laws)$

$$=x(x-1)S_1$ (since we showed that $(x-1)S_1 = x^{2n}-1$)$

$$=S_1$ (since we showed that $x(x-1)=1$)$

$and so $S_1$ is given by the sum $S$. $\blacksquare$$

pomsky · Oct 4, 2015

Thanks Integrand!

Quick Q though: how did you go from $(x-1)S_1 = x^{2n}-1$ to $S=\sum_{r=1}^n \binom{n}{r}x^{r+1}=x\left(\sum_{r=1}^n \binom{n}{r}x^{r}\right)$ ?

pomsky · Oct 4, 2015

wait jks jks it's a show, not prove question <>
Which means you used the LHS/ RHS thingo right?

rand_althor · Oct 4, 2015

pomsky said:
Thanks Integrand! Quick Q though: how did you go from $(x-1)S_1 = x^{2n}-1$ to $S=\sum_{r=1}^n \binom{n}{r}x^{r+1}=x\left(\sum_{r=1}^n \binom{n}{r}x^{r}\right)$ ?

He established that $(x-1)S_1 = x^{2n}-1$ by using the sum of a geometric series. To get $S=\sum_{r=1}^n \binom{n}{r}x^{r+1}=x\left(\sum_{r=1}^n \binom{n}{r}x^{r}\right)$ he factored out $x$ from the sum. Is that what you were unsure about?

InteGrand · Oct 4, 2015

pomsky said:
Thanks Integrand! Quick Q though: how did you go from $(x-1)S_1 = x^{2n}-1$ to $S=\sum_{r=1}^n \binom{n}{r}x^{r+1}=x\left(\sum_{r=1}^n \binom{n}{r}x^{r}\right)$ ?

$I just established the fact $(x-1)S_1 = x^{2n}-1$ at the start since it'd be important later, and then I started off with the series $S=\sum_{r=1}^n \binom{n}{r}x^{r+1}$, and showed that it's equal to $S_1$ (the $(x-1)S_1 = x^{2n}-1$ step wasn't related to the $S=\sum_{r=1}^n \binom{n}{r}x^{r+1}$ part).$

pomsky · Oct 4, 2015

Sweet.

Nah, I was unsure about the jump cos misread Q and thought it was a 'Prove" question (in which case I'm told , we wouldn't be able to do the LHS = RHS thingo. Is that true?)

What about this Q? (Perms and combs go over my head unfortunately. Trying to hammer out some before HSC haha)

Q: A sports committee consisting of four rowers, three basketballers and two cricketers sits at a circular table.
How many different arrangements of the committee are possible if the rowers and basketballers both sit together in groups, but no rower sits next to a basketballer?

Does this just mean that it's a group of rowers + cricketer + group of basketballers + cricketer?

rand_althor · Oct 4, 2015

pomsky said:
How many different arrangements of the committee are possible if the rowers and basketballers both sit together in groups, but no rower sits next to a basketballer?
Does this just mean that it's a group of rowers + cricketer + group of basketballers + cricketer?

Yep, that's the only setup which follows the conditions. What's the answer?

InteGrand · Oct 4, 2015

pomsky said:
Sweet. Nah, I was unsure about the jump cos misread Q and thought it was a 'Prove" question (which I'm told that in that case, we wouldn't be able to do the LHS = RHS thingo. It that true?)

$I actually did start at $S$ and went to $S_1$. By ``the LHS = RHS thingo'', do you mean doing a little bit to the L.H.S., a little bit to the R.H.S., and then showing they ``meet'' in the middle, i.e. if $LHS =X$ and $RHS = X$, then we have proved that $LHS = RHS$? This \textsl{is} a valid proof method, due to the symmetric and transitive properties of equality. And I don't think there's much difference between ``show'' and ``prove'' apart from that ``show'' is often used for 1-markers which are designed to get you to prove something that is easy to prove but will be used in a later part of the question, whilst ``prove'' is often used for proving longer or harder results. But it's valid to interchange ``show'' and ``prove'' I think (it's just semantics).$

pomsky · Oct 4, 2015

InteGrand said:
$I actually did start at $S$ and went to $S_1$. By ``the LHS = RHS thingo'', do you mean doing a little bit to the L.H.S., a little bit to the R.H.S., and then showing they ``meet'' in the middle, i.e. if $LHS =X$ and $RHS = X$, then we have proved that $LHS = RHS$? This \textsl{is} a valid proof method, due to the symmetric and transitive properties of equality. And I don't think there's much difference between ``show'' and ``prove'' apart from that ``show'' is often used for 1-markers which are designed to get you to prove something that is easy to prove but will be used in a later part of the question, whilst ``prove'' is often used for proving longer or harder results. But it's valid to interchange ``show'' and ``prove'' I think (it's just semantics).$

Sweet again x) How I've been taught is that my teachers recommend articulating LHS = RHS in 'show' questions (usually subbing or some manipulating, whereas for 'prove' questions, they recommend that I move from LHS to RHS in one direction only. (if that makes sense?)

But you're right, it's probably semantics ahaha.

In that case, for the perms and combs Q, would it be (4-1)!*2! (to move the cricketers) *4! (to move the rowers) *3! (to move the basketballers?)

InteGrand · Oct 4, 2015

pomsky said:
Sweet again x) How I've been taught is that my teachers recommend articulating LHS = RHS in 'show' questions (usually subbing or some manipulating, whereas for 'prove' questions, they recommend that I move from LHS to RHS in one direction only. (if that makes sense?)

But you're right, it's probably semantics ahaha.

In that case, for the perms and combs Q, would it be (4-1)!*2! (to move the cricketers) *4! (to move the rowers) *3! (to move the basketballers?)

$It should just be $2\times 3! \times 4!$. If the $B$'s (basketballers) and $R$'s (rowers) are to sit in groups but no $R$ is next to a $B$, then we must have in the circle the following type arrangement:$

----B
C₁----C₂
----R

(hopefully that diagram makes sense (the ---'s are just there to fill up space since just using spacebar doesn't seem to work)

$In the diagram, $B$ refers to the group of three basketballers and $R$ refers to the group of four rowers. So we need the two cricketers to be ``opposite'' each other in that diagram in order for $B$ and $R$ to \textit{not} be next to each other (which is meant by no rower being next to a basketballer). So we can fix $C_1$'s position in that circle, and then $C_2$ is automatically fixed. We can arrange the position of $B$ and $R$ in \fbox{2} ways; one way is in the diagram above, and the other way is simply interchanging them, i.e.:$

----R
C₁----C₂
----B.

$And for each of these arrangmenets, we can arrange the members in $R$ in \boxed{4!} ways, and the members in $B$ in \boxed{3!} ways. So the answer is \boxed{$2\times 4! \times 3! = 288$}.$

How do you find the margin of error in Newton's method? (1 Viewer)

pomsky

Active Member

rand_althor

Active Member

pomsky

Active Member

rand_althor

Active Member

pomsky

Active Member

InteGrand

Well-Known Member

pomsky

Active Member

pomsky

Active Member

rand_althor

Active Member

InteGrand

Well-Known Member

pomsky

Active Member

rand_althor

Active Member

InteGrand

Well-Known Member

pomsky

Active Member

InteGrand

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)