Mixing
Rearranging to get an iterative function (fixed point)
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I don't quite get why things are rearranged the way they are when trying to get an equation to be used in fixed point iteration. For example,
$x^3+2x+5=0$
could be rearranged to give
$:x=-frac5x^2+2:or:x=-sqrt[3]2x+5$
But apparently not
$x=-fracx^3+52$.
Why so?
algebra-precalculus fixed-point-theorems
asked Aug 6 at 0:32
Cheks Nweze
697
add a comment |Â
up vote
1
down vote
favorite
I don't quite get why things are rearranged the way they are when trying to get an equation to be used in fixed point iteration. For example,
$x^3+2x+5=0$
could be rearranged to give
$:x=-frac5x^2+2:or:x=-sqrt[3]2x+5$
But apparently not
$x=-fracx^3+52$.
Why so?
algebra-precalculus fixed-point-theorems
asked Aug 6 at 0:32
Cheks Nweze
697
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I don't quite get why things are rearranged the way they are when trying to get an equation to be used in fixed point iteration. For example,
$x^3+2x+5=0$
could be rearranged to give
$:x=-frac5x^2+2:or:x=-sqrt[3]2x+5$
But apparently not
$x=-fracx^3+52$.
Why so?
algebra-precalculus fixed-point-theorems
asked Aug 6 at 0:32
Cheks Nweze
697
I don't quite get why things are rearranged the way they are when trying to get an equation to be used in fixed point iteration. For example,
$x^3+2x+5=0$
could be rearranged to give
$:x=-frac5x^2+2:or:x=-sqrt[3]2x+5$
But apparently not
$x=-fracx^3+52$.
Why so?
algebra-precalculus fixed-point-theorems
asked Aug 6 at 0:32
Cheks Nweze
697
asked Aug 6 at 0:32
Cheks Nweze
697
asked Aug 6 at 0:32
Cheks Nweze
697
asked Aug 6 at 0:32
Cheks Nweze
697
697
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
The problem is that you generally want the fixed point iteration mapping to be contractive, at least in a neighborhood of the fixed point. Otherwise you start with a small error and end up with a larger error.
The situation is easier to see in a case where the exact solution of the equation is easily constructed. Look at something like $x^2-x-12=0$, and you're trying to find the root $x=4$. If you use $x=x^2-12$, the problem is that although indeed $4=4^2-12$ (i.e. the desired solution is a fixed point of the mapping), if you have an $x$ close to $4$ instead, $x^2-12$ is generally further away from $4$ than $x$ was. For example $3.9^2-12=3.21$.
The standard way to check this is to compute the absolute value of the derivative of the fixed point function at the fixed point, which in this example is $8$. If it is larger than $1$, then the mapping is not contractive near the fixed point, so the iteration (usually) does not converge.
answered Aug 6 at 0:37
Ian
65.2k24681
So does this mean that I can just move the $x$ term to one side, isolate $x$ and use that as a function as long as the derivative of the function at the fixed point is $-1<x<1$? Because in textbooks they seem to never just get the $x$ term on its own immediately, they usually just factorise $x$ out then rearrange or take a cube root.
– Cheks Nweze
Aug 6 at 0:50
1
@CheksNweze Yes, that's right. There is nothing mathematically incorrect about isolating $x$ from the linear term rather than, say, the leading order term of a polynomial equation. It just often leads to non-contractive mappings in practice.
– Ian
Aug 6 at 0:59
add a comment |Â
up vote
1
down vote
The key idea is to rewrite $f(x)=0$ in the form $x=phi(x)$ such that $vert phi'(x)vert <1$ for some $x$ in the vicinity of the root.
The picture above depicts the iteration process $x_n+1=phi(x_n)$ for $n=0,1,2,...$ which guarantees the convergence as $vert phi'(x)vert <1$ as the movement along the cobweb cycle indeed takes you towards the point of intersection of the curves.
You can easily see by drawing the graph that the iteration may diverge (this time the cobweb cycle will take you away from the point of intersection of the curves) rather if we relax the condition $vert phi'(x)vert <1$.
answered Aug 6 at 7:18
Mathlover
3,5831021
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
The problem is that you generally want the fixed point iteration mapping to be contractive, at least in a neighborhood of the fixed point. Otherwise you start with a small error and end up with a larger error.
The situation is easier to see in a case where the exact solution of the equation is easily constructed. Look at something like $x^2-x-12=0$, and you're trying to find the root $x=4$. If you use $x=x^2-12$, the problem is that although indeed $4=4^2-12$ (i.e. the desired solution is a fixed point of the mapping), if you have an $x$ close to $4$ instead, $x^2-12$ is generally further away from $4$ than $x$ was. For example $3.9^2-12=3.21$.
The standard way to check this is to compute the absolute value of the derivative of the fixed point function at the fixed point, which in this example is $8$. If it is larger than $1$, then the mapping is not contractive near the fixed point, so the iteration (usually) does not converge.
answered Aug 6 at 0:37
Ian
65.2k24681
So does this mean that I can just move the $x$ term to one side, isolate $x$ and use that as a function as long as the derivative of the function at the fixed point is $-1<x<1$? Because in textbooks they seem to never just get the $x$ term on its own immediately, they usually just factorise $x$ out then rearrange or take a cube root.
– Cheks Nweze
Aug 6 at 0:50
1
@CheksNweze Yes, that's right. There is nothing mathematically incorrect about isolating $x$ from the linear term rather than, say, the leading order term of a polynomial equation. It just often leads to non-contractive mappings in practice.
– Ian
Aug 6 at 0:59
add a comment |Â
up vote
3
down vote
accepted
The problem is that you generally want the fixed point iteration mapping to be contractive, at least in a neighborhood of the fixed point. Otherwise you start with a small error and end up with a larger error.
The situation is easier to see in a case where the exact solution of the equation is easily constructed. Look at something like $x^2-x-12=0$, and you're trying to find the root $x=4$. If you use $x=x^2-12$, the problem is that although indeed $4=4^2-12$ (i.e. the desired solution is a fixed point of the mapping), if you have an $x$ close to $4$ instead, $x^2-12$ is generally further away from $4$ than $x$ was. For example $3.9^2-12=3.21$.
The standard way to check this is to compute the absolute value of the derivative of the fixed point function at the fixed point, which in this example is $8$. If it is larger than $1$, then the mapping is not contractive near the fixed point, so the iteration (usually) does not converge.
answered Aug 6 at 0:37
Ian
65.2k24681
So does this mean that I can just move the $x$ term to one side, isolate $x$ and use that as a function as long as the derivative of the function at the fixed point is $-1<x<1$? Because in textbooks they seem to never just get the $x$ term on its own immediately, they usually just factorise $x$ out then rearrange or take a cube root.
– Cheks Nweze
Aug 6 at 0:50
1
@CheksNweze Yes, that's right. There is nothing mathematically incorrect about isolating $x$ from the linear term rather than, say, the leading order term of a polynomial equation. It just often leads to non-contractive mappings in practice.
– Ian
Aug 6 at 0:59
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
The problem is that you generally want the fixed point iteration mapping to be contractive, at least in a neighborhood of the fixed point. Otherwise you start with a small error and end up with a larger error.
The situation is easier to see in a case where the exact solution of the equation is easily constructed. Look at something like $x^2-x-12=0$, and you're trying to find the root $x=4$. If you use $x=x^2-12$, the problem is that although indeed $4=4^2-12$ (i.e. the desired solution is a fixed point of the mapping), if you have an $x$ close to $4$ instead, $x^2-12$ is generally further away from $4$ than $x$ was. For example $3.9^2-12=3.21$.
The standard way to check this is to compute the absolute value of the derivative of the fixed point function at the fixed point, which in this example is $8$. If it is larger than $1$, then the mapping is not contractive near the fixed point, so the iteration (usually) does not converge.
answered Aug 6 at 0:37
Ian
65.2k24681
The problem is that you generally want the fixed point iteration mapping to be contractive, at least in a neighborhood of the fixed point. Otherwise you start with a small error and end up with a larger error.
The situation is easier to see in a case where the exact solution of the equation is easily constructed. Look at something like $x^2-x-12=0$, and you're trying to find the root $x=4$. If you use $x=x^2-12$, the problem is that although indeed $4=4^2-12$ (i.e. the desired solution is a fixed point of the mapping), if you have an $x$ close to $4$ instead, $x^2-12$ is generally further away from $4$ than $x$ was. For example $3.9^2-12=3.21$.
The standard way to check this is to compute the absolute value of the derivative of the fixed point function at the fixed point, which in this example is $8$. If it is larger than $1$, then the mapping is not contractive near the fixed point, so the iteration (usually) does not converge.
answered Aug 6 at 0:37
Ian
65.2k24681
answered Aug 6 at 0:37
Ian
65.2k24681
answered Aug 6 at 0:37
Ian
65.2k24681
answered Aug 6 at 0:37
Ian
65.2k24681
65.2k24681
So does this mean that I can just move the $x$ term to one side, isolate $x$ and use that as a function as long as the derivative of the function at the fixed point is $-1<x<1$? Because in textbooks they seem to never just get the $x$ term on its own immediately, they usually just factorise $x$ out then rearrange or take a cube root.
– Cheks Nweze
Aug 6 at 0:50
1
@CheksNweze Yes, that's right. There is nothing mathematically incorrect about isolating $x$ from the linear term rather than, say, the leading order term of a polynomial equation. It just often leads to non-contractive mappings in practice.
– Ian
Aug 6 at 0:59
add a comment |Â
So does this mean that I can just move the $x$ term to one side, isolate $x$ and use that as a function as long as the derivative of the function at the fixed point is $-1<x<1$? Because in textbooks they seem to never just get the $x$ term on its own immediately, they usually just factorise $x$ out then rearrange or take a cube root.
– Cheks Nweze
Aug 6 at 0:50
1
@CheksNweze Yes, that's right. There is nothing mathematically incorrect about isolating $x$ from the linear term rather than, say, the leading order term of a polynomial equation. It just often leads to non-contractive mappings in practice.
– Ian
Aug 6 at 0:59
So does this mean that I can just move the $x$ term to one side, isolate $x$ and use that as a function as long as the derivative of the function at the fixed point is $-1<x<1$? Because in textbooks they seem to never just get the $x$ term on its own immediately, they usually just factorise $x$ out then rearrange or take a cube root.
– Cheks Nweze
Aug 6 at 0:50
So does this mean that I can just move the $x$ term to one side, isolate $x$ and use that as a function as long as the derivative of the function at the fixed point is $-1<x<1$? Because in textbooks they seem to never just get the $x$ term on its own immediately, they usually just factorise $x$ out then rearrange or take a cube root.
– Cheks Nweze
Aug 6 at 0:50
1
1
@CheksNweze Yes, that's right. There is nothing mathematically incorrect about isolating $x$ from the linear term rather than, say, the leading order term of a polynomial equation. It just often leads to non-contractive mappings in practice.
– Ian
Aug 6 at 0:59
@CheksNweze Yes, that's right. There is nothing mathematically incorrect about isolating $x$ from the linear term rather than, say, the leading order term of a polynomial equation. It just often leads to non-contractive mappings in practice.
– Ian
Aug 6 at 0:59
add a comment |Â
up vote
1
down vote
The key idea is to rewrite $f(x)=0$ in the form $x=phi(x)$ such that $vert phi'(x)vert <1$ for some $x$ in the vicinity of the root.
The picture above depicts the iteration process $x_n+1=phi(x_n)$ for $n=0,1,2,...$ which guarantees the convergence as $vert phi'(x)vert <1$ as the movement along the cobweb cycle indeed takes you towards the point of intersection of the curves.
You can easily see by drawing the graph that the iteration may diverge (this time the cobweb cycle will take you away from the point of intersection of the curves) rather if we relax the condition $vert phi'(x)vert <1$.
answered Aug 6 at 7:18
Mathlover
3,5831021
add a comment |Â
up vote
1
down vote
The key idea is to rewrite $f(x)=0$ in the form $x=phi(x)$ such that $vert phi'(x)vert <1$ for some $x$ in the vicinity of the root.
The picture above depicts the iteration process $x_n+1=phi(x_n)$ for $n=0,1,2,...$ which guarantees the convergence as $vert phi'(x)vert <1$ as the movement along the cobweb cycle indeed takes you towards the point of intersection of the curves.
You can easily see by drawing the graph that the iteration may diverge (this time the cobweb cycle will take you away from the point of intersection of the curves) rather if we relax the condition $vert phi'(x)vert <1$.
answered Aug 6 at 7:18
Mathlover
3,5831021
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The key idea is to rewrite $f(x)=0$ in the form $x=phi(x)$ such that $vert phi'(x)vert <1$ for some $x$ in the vicinity of the root.
The picture above depicts the iteration process $x_n+1=phi(x_n)$ for $n=0,1,2,...$ which guarantees the convergence as $vert phi'(x)vert <1$ as the movement along the cobweb cycle indeed takes you towards the point of intersection of the curves.
You can easily see by drawing the graph that the iteration may diverge (this time the cobweb cycle will take you away from the point of intersection of the curves) rather if we relax the condition $vert phi'(x)vert <1$.
answered Aug 6 at 7:18
Mathlover
3,5831021
The key idea is to rewrite $f(x)=0$ in the form $x=phi(x)$ such that $vert phi'(x)vert <1$ for some $x$ in the vicinity of the root.
The picture above depicts the iteration process $x_n+1=phi(x_n)$ for $n=0,1,2,...$ which guarantees the convergence as $vert phi'(x)vert <1$ as the movement along the cobweb cycle indeed takes you towards the point of intersection of the curves.
You can easily see by drawing the graph that the iteration may diverge (this time the cobweb cycle will take you away from the point of intersection of the curves) rather if we relax the condition $vert phi'(x)vert <1$.
answered Aug 6 at 7:18
Mathlover
3,5831021
edited Aug 6 at 8:24
answered Aug 6 at 7:18
Mathlover
3,5831021
answered Aug 6 at 7:18
Mathlover
3,5831021
answered Aug 6 at 7:18
Mathlover
3,5831021
3,5831021
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873465%2frearranging-to-get-an-iterative-function-fixed-point%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password