Cheap and Secure Web Hosting Provider : See Now

Prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values

, , No Comments
Problem Detail: 

How can I prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values ?

It seems obvious to me, since an ill-conditioned problem is that in which exact input values(D) are totally different from error valuesI(D') (judging by something), thus the exact solution(G) differ much from one with error in some sense. This can be applied in case of algorithms: because if D and D' are far from each other somehow, than no one can expect for G(D*) to get closer to G*(D), where G* is the algorithm for implementing the G problem . Can you please show some more precise approach, less "in words" and more in logic ?

Thank you.

Asked By : Gandacov I.

Answered By : w00d

Let's try to define those terms in math language:

  • Denote $x$ as the input, and $f(x)$ is the solution to the problem with input $x$.
  • Ill-condition problem: $x'=x + \delta \Rightarrow f(x') \gg f(x) + \delta$
  • Stable algorithm $F(x) \simeq f(x')$ (stable algorithm give you result close to result of a nearby input)

So apply stable algorithm on ill-condition problem we get: $F(x) \simeq f(x') \gg f(x) + \delta$

Which says the best you can get can't be smaller than error in the input.

I think you can also prove by contradiction, saying if the stable algorithm can do that, then the changes in input will make only small change in the output which makes the problem well-condition.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40002

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback