|
|
| Author |
Message |
Fijoy George
science forum beginner
Joined: 15 May 2005
Posts: 17
|
 Posted: Fri Jun 23, 2006 3:43 am Post subject:
Well conditioned problems and stable methods
|
|
|
Hi all,
Could anyone help me with the following question?
Does a well-conditioned problem always has a stable numerical algorithm to
solve it? If not, could you give an example for a well-conditioned problem
with no stable solution method?
Thank you
Fijoy |
|
| Back to top |
|
 |
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Fri Jun 23, 2006 8:46 am Post subject:
Re: Well conditioned problems and stable methods
|
|
|
Fijoy George wrote:
| Quote: | Does a well-conditioned problem always has a stable numerical algorithm to
solve it? If not, could you give an example for a well-conditioned problem
with no stable solution method?
|
Take the second order ordinary differential equation:
a.d^2u/dx^2 + b.du/dx + c.u = 0
And assume that b^2 - 4.a.c < 0 . Then no stable solution method exists
numerically. (How else would you deal with the wiggles?) Stable solution
methods exist only for b^2 - 4.a.c >= 0 . The whole thing is proven in:
http://hdebruijn.soo.dto.tudelft.nl/hdb_spul/calculus.pdf
http://huizen.dto.tudelft.nl/deBruijn/grondig/calculus.htm
Han de Bruijn |
|
| Back to top |
|
|
Peter Spellucci
science forum Guru
Joined: 29 Apr 2005
Posts: 702
|
| Posted: Fri Jun 23, 2006 5:34 pm Post subject:
Re: Well conditioned problems and stable methods
|
|
|
In article <e7fkgp$b8m$1@mailhub227.itcs.purdue.edu>,
"Fijoy George" <tofijoy@yahoo.co.in> writes:
| Quote: | Hi all,
Could anyone help me with the following question?
Does a well-conditioned problem always has a stable numerical algorithm to
solve it? If not, could you give an example for a well-conditioned problem
with no stable solution method?
Thank you
Fijoy
|
thereare so many notions of stability such that we first have do define
some terms (han de bruin obviously answered with stability something like strongly
dissipative in mind)
Def1: a problem is a map from R^n to R^m which can be written as
y=F(x) with F explicitly or implitly defined .
in the following we restrict ourselves to a F which is a rational function
of the x_i and at least C^1 .
Def2: an algorithm is a collection of sequences of elementary maps
Phi: P_1 -> P_2 -> P_3 ..... -> P_M
each P_i being a map from some R^k to some R^l , with each component
j of P_i being of the form
P_{i,j} = x(s_i) op x(s_j) or x(s_i) or -x(s_i)
with s_i,s_j in {1,...,n_i} with n_i the dimension of the range of P_i
and op in {+,-,*,/}
the sequence itself possibly dependent on the input x.
or in simpler terms: each component of P_i is an elementary arithmetic
operation or the identity or -identity and there may be branches in the
computational graph
Def3: An algorithm Phi for a problem given by F is defined by
F(x)=Phi(x) for x in D
Def4: round(x) denotes the rounding of a real number to the number
representation used in fl_op, the computer arithmetic
Def5: we associate a numerical algorithm to an algorithm by replacing
op by fl_op , fl_op denoting the computer arithmetic
Def6: an algorithm for problem F is stable on D subset of range of F
with respect to two norms in range F (||.||_1) and image F (||.||_2)
if for all inputs x in D
||F(round(x)) - P_M(round(P_{M-1}(round(...... P_1(round(x))...) ||_2
<= C*eps*(||F(x)||_2 + ||DF(x)||_{2,1}||x-round(x)||_1 )
for some constant C(n,m,D) , with eps defined as
eps = sup{ x: fl(1+x)=1 }
or, in simple words, if the net effect of all rounding errors
occuring in the numerical algorithm is not essentially worse than
than the effect of perturbing the input a little and then computing anything
exactly
even for this seemingly simple setting the question is open.
(for other, clearly more interesting problems additional processes must be added
like discretization, truncation, approximation ...)
the reason is this:
the net effect of the errors in the algorithm is something like
eps*( sum_{i=1 to M}
( norm(prod_{j=i to M} Jacobian(P_j)) ||P_i(....(P_1(x)..)|| ) )
and one were forced to prove that there always exists a decomposition of
F into elementary maps such that the norms of the Jacobians and the intermediate
results satisfy this condition)
if the algorithm is backward stable in the sense of Wilkinson then it is stable
in the sense above.
one rule of thumb to reach this goal is the E. Stiefels principle of
"direct attack" (avoid mathematical transformations of the problem, solve it
in its original setting)
maybe your question has a more specific background, then there is a hope for a
more specific answer
hth
peter |
|
| Back to top |
|
|
bv
science forum addict
Joined: 16 May 2005
Posts: 59
|
| Posted: Sat Jul 01, 2006 5:34 am Post subject:
Re: Well conditioned problems and stable methods
|
|
|
Han de Bruijn wrote:
| Quote: |
Does a well-conditioned problem always has a stable numerical algorithm to
solve it? If not, could you give an example for a well-conditioned problem
with no stable solution method?
Take the second order ordinary differential equation:
a.d^2u/dx^2 + b.du/dx + c.u = 0
And assume that b^2 - 4.a.c < 0 . Then no stable solution method exists
numerically. (How else would you deal with the wiggles?) Stable solution
methods exist only for b^2 - 4.a.c >= 0 .
|
Either matrix exponential or z-transform method would give you a
numerically stable solution as long the ode is stable. i.e. -b/2a < 0.
There may be a problem calculating either in case of extreme valued
coefficients, but that's another topic - look for "nineteen dubious
ways..." to learn why 25 years latter they're still looking for the
undubious way.
---
sdx - modeling, simulation
http://www.sdynamix.com |
|
| Back to top |
|
|
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Sat Jul 01, 2006 12:28 pm Post subject:
Re: Well conditioned problems and stable methods
|
|
|
Peter Spellucci wrote:
| Quote: | thereare so many notions of stability such that we first have do define
some terms (han de bruin obviously answered with stability something
like strongly dissipative in mind)
|
http://hdebruijn.soo.dto.tudelft.nl/hdb_spul/calculus.pdf
In the abovementioned paper, the formulation of the problem results in
a tridiagonal system of linear equations to be solved. It can be shown
that pivoting the equations is "dangerous" (i.e. pivot can become zero
and, by Murphy's law, it will) for O.D.E.'s
a.d^2u/dx^2 + b.du/dx + c.u = 0 with (b^2 - 4.a.c) < 0 .
Han de Bruijn |
|
| Back to top |
|
|
Peter Spellucci
science forum Guru
Joined: 29 Apr 2005
Posts: 702
|
| Posted: Mon Jul 03, 2006 1:41 pm Post subject:
Re: Well conditioned problems and stable methods
|
|
|
In article <1151756899.673906.263990@m73g2000cwd.googlegroups.com>,
Han.deBruijn@DTO.TUDelft.NL writes:
| Quote: | Peter Spellucci wrote:
thereare so many notions of stability such that we first have do define
some terms (han de bruin obviously answered with stability something
like strongly dissipative in mind)
http://hdebruijn.soo.dto.tudelft.nl/hdb_spul/calculus.pdf
In the abovementioned paper, the formulation of the problem results in
a tridiagonal system of linear equations to be solved. It can be shown
that pivoting the equations is "dangerous" (i.e. pivot can become zero
and, by Murphy's law, it will) for O.D.E.'s
a.d^2u/dx^2 + b.du/dx + c.u = 0 with (b^2 - 4.a.c) < 0 .
Han de Bruijn
|
yes, but this does not answer the question of the original poster:
for a stable problem does there always exist a stable algorithm?
you simply have the fact that the standard second order fd becomes
unstable in this situation, (and, besides, also the original boundary value
problem can be unstable or even unsolvable then)
hth
peter |
|
| Back to top |
|
|
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Mon Jul 03, 2006 2:36 pm Post subject:
Re: Well conditioned problems and stable methods
|
|
|
Peter Spellucci wrote:
| Quote: | yes, but this does not answer the question of the original poster:
for a stable problem does there always exist a stable algorithm?
|
No, in the the original poster it is stated that:
| Quote: | Does a well-conditioned problem always has a stable numerical algorithm to
solve it? If not, could you give an example for a well-conditioned problem
with no stable solution method?
|
And the answer to _that_ question is: NO.
You are asking a quite different question:
| Quote: | for a stable problem does there always exist a stable algorithm?
|
And the answer to that question is: yes. Simply because it's a vicious
circle definition that problems are stable iff they can be solved with
a stable algorithm.
Han de Bruijn |
|
| Back to top |
|
|
Peter Spellucci
science forum Guru
Joined: 29 Apr 2005
Posts: 702
|
| Posted: Mon Jul 03, 2006 3:20 pm Post subject:
Re: Well conditioned problems and stable methods
|
|
|
In article <91a76$44a92b59$82a1e228$32238@news1.tudelft.nl>,
Han de Bruijn <Han.deBruijn@DTO.TUDelft.NL> writes:
| Quote: | Peter Spellucci wrote:
yes, but this does not answer the question of the original poster:
for a stable problem does there always exist a stable algorithm?
No, in the the original poster it is stated that:
Does a well-conditioned problem always has a stable numerical algorithm to
solve it? If not, could you give an example for a well-conditioned problem
with no stable solution method?
And the answer to _that_ question is: NO.
You are asking a quite different question:
for a stable problem does there always exist a stable algorithm?
And the answer to that question is: yes. Simply because it's a vicious
circle definition that problems are stable iff they can be solved with
a stable algorithm.
Han de Bruijn
|
NO!!!!
a problem is stable if a small perturbation of its input (coefficients,
right hand side, for an ode: boundary conditions, coefficients) results in
a small change in the solution , in the Lipschitz continuous sense.
it is not obvious, that every such problem can be broken down to
a sequence of approximations and elementary arithmetic operations
such that the net effect of perturbations in these steps results also
in a small perturbation of the solution.
hth
peter |
|
| Back to top |
|
|
Han de Bruijn
science forum Guru
Joined: 18 May 2005
Posts: 1285
|
| Posted: Tue Jul 04, 2006 6:55 am Post subject:
Re: Well conditioned problems and stable methods
|
|
|
Peter Spellucci wrote:
| Quote: | NO!!!!
a problem is stable if a small perturbation of its input (coefficients,
right hand side, for an ode: boundary conditions, coefficients) results in
a small change in the solution , in the Lipschitz continuous sense.
it is not obvious, that every such problem can be broken down to
a sequence of approximations and elementary arithmetic operations
such that the net effect of perturbations in these steps results also
in a small perturbation of the solution.
|
OK. Thus a problem is _un_stable if a small perturbation of its input
results in a _large_ change in the solution. A numerical approximation
can be considered as such a "small perturbation of its input". Shall we
conclude then in the first place: that there exists no stable algorithm
for an unstable problem?
But the reverse is also true. If a problem is stable for _all_ possible
small perturbations, then a "proper" numerical method - just being such
a "small" perturbation, by definition - must lead to a stable solution.
No? Am I missing something here?
Han de Bruijn |
|
| Back to top |
|
|
Peter Spellucci
science forum Guru
Joined: 29 Apr 2005
Posts: 702
|
| Posted: Tue Jul 04, 2006 4:39 pm Post subject:
Re: Well conditioned problems and stable methods
|
|
|
In article <42fb5$44aa10d6$82a1e228$17179@news2.tudelft.nl>,
Han de Bruijn <Han.deBruijn@DTO.TUDelft.NL> writes:
| Quote: | Peter Spellucci wrote:
NO!!!!
a problem is stable if a small perturbation of its input (coefficients,
right hand side, for an ode: boundary conditions, coefficients) results in
a small change in the solution , in the Lipschitz continuous sense.
it is not obvious, that every such problem can be broken down to
a sequence of approximations and elementary arithmetic operations
such that the net effect of perturbations in these steps results also
in a small perturbation of the solution.
OK. Thus a problem is _un_stable if a small perturbation of its input
results in a _large_ change in the solution. A numerical approximation
can be considered as such a "small perturbation of its input". Shall we
conclude then in the first place: that there exists no stable algorithm
for an unstable problem?
But the reverse is also true. If a problem is stable for _all_ possible
small perturbations, then a "proper" numerical method - just being such
a "small" perturbation, by definition - must lead to a stable solution.
No? Am I missing something here?
Han de Bruijn
|
think about this:
one knows that a hermitian perturbation of a hermitian matrix
perturbs the eigenvalues no more than the 2-norm of the perturbation matrix,
that means the eigenvalues of a hermitian matrix are stable under perturbations.
but now someone comes along and computes first the characteristic polynomial
in the monomial representation , then the eigenvalues as the zeros of this
polynomial. depending on the distribution of the eigenvalues this can
result in catastrophically erroneous eigenvalues: although a mathematically
correct procedure under exact arithmetic the perturbations introduced by this
problem decomposition is unstable. I think the original questioner was
interested in this question: given a stable problem, exists there always a stable
algorithm for implementing it.
hth
peter |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 1:57 am | All times are GMT
|
|
Free Advertising | eBay | Bankruptcy | Credit Counseling | Christmas Layouts
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
num-analysis
