Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Was genau ist ein schlecht konditioniertes Problem?
Autor
Universität/Hochschule Was genau ist ein schlecht konditioniertes Problem?
Pter87
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.11.2018
Mitteilungen: 413
  Themenstart: 2021-11-30

Was heißt es denn im praktischen Sinne, wenn ein Problem schlecht konditioniert ist? Ich weiß nicht so recht, was oftmals mit "Problem" gemeint ist. Wenn man jetzt "Problem" ganz abstrakt fasst, dann müsste man doch erstmal unterscheiden zwischen der Kondition des Problems und der Kondition des mathematischen Modells, welches das Problem beschreibt. Dann hätte man ja im Grunde eine solche Kette: Problem -> Modell -> Algorithmus -> Lösung Die Frage ist, inwiefern die Kondition des Problems allgemein etwas über die Kondition des mathematischen Modells aussagt, z.B. sowas wie: Kondition des Problems schlecht $\Rightarrow$ Kondition aller mathematischen Modelle bezüglich dieses Problems sind schlecht Man könnte ja das Standardbeispiel dazu nehmen. Man nehme zwei hinreichend parallele Geraden und soll den Schnittpunkt finden. Das Problem ist ja dahingehend, wenn man sich das kurz überlegt, für hinreichend parallele Geraden schlecht gestellt, da sich eine minimale Änderung der beiden Geraden im Computer den Schnittpunkt stark wandern lassen würde. Die Frage ist, ob so ein Problem intrinsisch "schlecht" ist bzw. ob es für das Problem ein gut konditioniertes mathematisches Modell gibt. Danke im Voraus


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1895
  Beitrag No.1, eingetragen 2021-11-30

Hallo Pter87! Es gibt Differentialgleichungen die sich numerisch schlecht lösen lassen. Wo eine Lösungsverfolgung(Anfangswertproblem) zu großen Fehlern führt. Ein Beispiel muss ich mal raussuchen! ... Hier kommt es: \ y''-10y'-11y = 0 y(0) = 1 y'(0) = -1 hat als Lösung y(x) = e^(-x) ist numerisch aber nicht gut lösbar! (Siehe: Golub/Ortega "Wissenschafliches Rechnen und Differentialgleichungen" S.57) Viele Grüße Ronald


   Profil
Pter87
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.11.2018
Mitteilungen: 413
  Beitrag No.2, vom Themenstarter, eingetragen 2021-12-01

Wie kam man eigentlich zu dem Entschluss, dass diese Funktion $y(x)= e^{-x}$ numerisch nicht gut lösbar ist? Nehmen wir mal ein LGS mit einer schlecht konditionierten Matrix. Da habe ich vor paar Tagen irgendwo gelesen, dass man da trotzdem irgendwelche Techniken nutzt, um das doch noch irgendwie numerisch gut hinzubekommen(ich hoffe ich hab da nichts missverstanden). Wie kann man aber jetzt bei einem Problem zu dem Entschluss kommen, dass es numerisch nicht gut lösbar ist. Könnte es nicht irgendwie sein, dass da irgendein total schlauer Typ mit einer Methode kommt, die das Problem numerisch irgendwie doch "brauchbar" gut löst?


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1895
  Beitrag No.3, eingetragen 2021-12-01

Hallo, \quoteon(2021-12-01 17:16 - Pter87 in Beitrag No. 2) Wie kam man eigentlich zu dem Entschluss, dass diese Funktion $y(x)= e^{-x}$ numerisch nicht gut lösbar ist? \quoteoff Angegeben ist die exakte Lösung. Numerisch gibt es Probleme, da ein Fehler Epsilon sehr stark vergrößert wird: (Golub/Ortega) \ y(0) = 1+ \epsilon, y'(0) = -1 y(x) = (1+(11/12 \epsilon)*e^(-x)+(\epsilon/12)*e^(11x) Viele Grüße Ronald


   Profil
Pter87
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.11.2018
Mitteilungen: 413
  Beitrag No.4, vom Themenstarter, eingetragen 2021-12-01

Achso, du meintest die Differentialgleichung sei numerisch schlecht lösbar... Was macht man denn, wenn das Problem eine sehr schlechte Kondition hat und man auch keine exakte Lösung hat? Soweit ich richtig gelesen habe, ist die Kondition eine Charakteristik des Problems und lässt sich nicht mit numerischen Methoden umgehen.


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1895
  Beitrag No.5, eingetragen 2021-12-01

Auch kann ein numerisches Verfahren Probleme bereiten. Das einfache Gauß-Verfahren zur Lösung linearer Gleichungen kann numerisch problematisch werden. siehe auch: https://de.wikipedia.org/wiki/Gaußsches_Eliminationsverfahren Edit: Mit dem Newton Verfahren im Komplexen kann man Fraktale erzeugen. Wie z.B. https://www.matheplanet.de/matheplanet/nuke/html/article.php?sid=1745 (Fraktal Nr. 14 oder 15)


   Profil
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3572
Wohnort: hier und dort (s. Beruf)
  Beitrag No.6, eingetragen 2021-12-01

Huhu Pter, \quoteon(2021-12-01 17:16 - Pter87 in Beitrag No. 2) Nehmen wir mal ein LGS mit einer schlecht konditionierten Matrix. Da habe ich vor paar Tagen irgendwo gelesen, dass man da trotzdem irgendwelche Techniken nutzt, um das doch noch irgendwie numerisch gut hinzubekommen(ich hoffe ich hab da nichts missverstanden). \quoteoff vermutlich hast Du etwas missverstanden. Die Kondition eines "Problems" (d.i. abstrakt lediglich eine Abbildung $f:X \to Y$) lässt sich für normierte Räume erklären und ist tatsächlich eine Charakteristik des Problems und lässt sich nicht durch kluge Tricks umgehen. Etwas ganz anderes ist es aber, dass man numerische Verfahren haben kann, die auch aus (relativ) gut konditionierten (relativ) schlecht konditionierte Teilprobleme entwickeln. Hier kann man natürlich etwas tun! Ein typisches Beispiel ist vielleicht die Finite-Elemente-Diskretisierung eines (Anfangs-)Randwertproblems einer partiellen Differentialgleichung. Durch die Diskretisierung entsteht (meist als Zwischenschritt) ein meist relativ schlecht konditioniertes Lineares Gleichungssystem $Ax = b$. Löst man dieses ohne Berücksichtigung der Kondition, so konvergiert der gesamte Algorithmus z.B. nur sehr langsam. Dies ist ein schlechtes numerisches Verfahren! Aber hier kann man durchaus etwas tun! $Ax = B$ hat die gleichen Lösungen wie $MAx = Mb$ (für $M$ von vollem Rang). Im Allgemeinen kann man natürlich kein solches $M$ einfach finden, aber im Beispiel der Diskretisierung einer PDE ist die Struktur von $A$ recht gut bekannt und so kann man $M$ etwa aus einer recht einfach zu berechnenenden, in der Praxis nahezu immer unvollständigen $LU$-Zerlegung von $A$ bestimmen und so die Kondition der Matrix $MA$ oft deutlich reduzieren bzw. das verwendete Verfahren numerisch stabilisieren und/oder beschleunigen. Ich denke, solche Dinge sind gemeint, wenn man die "Kondition eines Problems" verbessert. lg, AK [Die Antwort wurde nach Beitrag No.4 begonnen.]


   Profil
Pter87
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.11.2018
Mitteilungen: 413
  Beitrag No.7, vom Themenstarter, eingetragen 2021-12-02

Danke euch für die ganzen hilfreichen Beiträge, aber noch ist mir das nicht zu 100% klar. Auf StackExchange schreibt jemand: "To threat an ill-conditioned system there are two principal ways: preconditioning: using this technique you obtain a system mathematically equivalent to the start situation, but with a better condition number. ..." Auf der deutschen Wikipedia Seite steht: "In der numerischen Mathematik bezeichnet Vorkonditionierung eine Technik, mittels derer ein Problem so umgeformt wird, dass die Lösung erhalten bleibt, sich jedoch für das gewählte numerische Lösungsverfahren positive Eigenschaften wie bessere Kondition oder schnellere Konvergenz ergeben." Erstmal ist doch Kondition nicht für numerische Verfahren definiert oder? Trotzdem weckt die Ausdrucksweise bei mir den Anschein, als wenn er sagen will, dass das umgeformte Problem eine bessere Kondition hätte als das Alte. @AnnaKath Du hast geschrieben, dass sich die Kondition eines Problems nicht umgehen lasse, also sind die Aussagen von oben beide falsch?


   Profil
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3572
Wohnort: hier und dort (s. Beruf)
  Beitrag No.8, eingetragen 2021-12-02

Huhu Pter, die Aussagen sind nicht falsch. Ein "Problem" in der Numerik ist einfach eine Abbildung $f:X\to Y$ (man kann sich vorstellen, dass $y\in Y$ die Lösung zu einer Aufgabe mit "Inputdaten" $x\in X$ darstellt). Sind $X,Y$ normiert, so kann man etwa $\kappa = \lim_{x \to x_0} \sup \frac{\|f(x)-f(x_0\|}{\|x-x_0\|}$ für gegebenes $x_0$ definieren und als Kondition des Problems ansehen. Natürlich ist diese somit nicht "veränderlich". Allerdings kann man, wie im Beispiel der Vorkonditionierung, ggf. Probleme finden, die einem gewissen Sinne äquivalent sind und numerisch "günstiger sind". D.h. dass es eine Funktion $h:X\to Z$ gibt und ein "Problem" (bzw. hier wohl mehr ein "Verfahren") $g:Z\to Y$. sodass $h \circ g = f$ und $g$ eine bessere Kondition (als $f$) hat. lg, AK


   Profil
Pter87
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.11.2018
Mitteilungen: 413
  Beitrag No.9, vom Themenstarter, eingetragen 2021-12-02

Nehmen wir mal das konkrete Problem $Ax = y$. Wäre dann in dem Fall $\mathbf{X}$ ein 2-er Tupel mit Matrizen als Einträgen und $\mathbf{Y}$ der Raum der Vektoren (das alles sei dimensionsverträglich mit dem Ursprungsproblem). Ich würde dann definieren: $f\colon \mathbf{X} \to \mathbf{Y},\quad (A,b) \mapsto A^{-1}b$ Die Lösung für unser Problem wäre dann $f((A,y))$. Und bezüglich dieser Funktion könnte ich dann eine Kondition definieren?


   Profil
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3572
Wohnort: hier und dort (s. Beruf)
  Beitrag No.10, eingetragen 2021-12-02

Huhu Pter, nun, im Sinne der o.a. Definition könnte man etwa $X=\mathbb{R}^n$ und $Y=\mathbb{R}^n$ haben (sofern $A$ eine quadratische $n\times n$-Matrix von vollem Rang ist). $f$ ist dann tatsächlich gegeben durch $f(b) = A^{-1}b$. Bzgl. eines gegebenen $b_0 \in X$ kann man dann die Kondition definieren, die in diesem Falle wohl mit der Kondition der Matrix übereinstimmt. Um ehrlich zu sein: Zumindest in meinem "mathematischen" Leben bin ich nur dem Begriff der Kondition in genau einem Falle begegnet - nämlich dem oben geschilderten. Genauer ist dies auch nur im Falle von Vorkonditionierung bei Krylow-Unterraum-Lösern für die linearen Gleichungssysteme, die sich aus der DIskretisierung von partiellen Differentialgleichung ergeben, praktisch relevant gewesen. Es ist also möglich, dass die Verallgemeinerung des Begriffs der Kondition recht künstlich ist und im Grunde nur versucht, die Matrixkondition etwas "schicker" zu verpacken. lg, AK


   Profil
piquer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2013
Mitteilungen: 506
  Beitrag No.11, eingetragen 2021-12-03

Hallo AK, die Konditionszahl eines linearen Problems ist fundamental in dem Sinne, dass es viele Möglichkeiten gibt, sie zu berechnen oder Abschätzungen dazu zu geben. All das ist bei nichtlinearen Problemen nicht möglich. Allerdings ist hier das Newton-Verfahren das bevorzugte Verfahren, in dem auch in jedem Schritte ein lineares Problem gelöst werden muss. Ein prominentes Beispiel zur Konditionszahl des allgemeinen (linearen oder nichtlinearen) Interpolationsproblems auf einem äquidistanten Gitter findet sich in diesem Artikel. Darin wird die Unmöglichkeit der exponentiell konvergenten Polynominterpolation bei nicht exponentiell wachsender Konditionszahl beschrieben. Viele Grüße Torsten


   Profil
Pter87 hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]