Forum: PC-Programmierung Iterative Lösung nichtlinearer gleichungen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Carol Z. (Gast)


Lesenswert?

Ich habe eine Gleichung x = g(x) die nicht algebraisch für x lösbar ist. 
Wie kann man am besten in c++ solche Gleichungen iterativ lösen? Ich 
hatte mich mal mit der dlib beschäftigt und im Prinzip muss man doch x - 
g(x) = 0 lösen, oder? Wie würde denn die objektive Funktion dafür 
aussehen?

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Nix genaues weiß man nicht.

Ist die Funktion über R definiert?
Über R^n?
Über Z?
Stetig?
Differenzierbar?

von Carol Z. (Gast)


Lesenswert?

Johann L. schrieb:
> Nix genaues weiß man nicht.
> Ist die Funktion über R definiert?
> Über R^n?
> Über Z?
> Stetig?
> Differenzierbar?

0 hat eine Polstelle sonst differenzierbar und potenzierbar. Da gehen 
auch keine komplexen Werte rein.

von Maxe (Gast)


Lesenswert?

Reicht eine Lösung?

Newton-Verfahren?

von Elektrofan (Gast)


Lesenswert?

Regula falsi?

von Rechenmonster (Gast)


Lesenswert?

Wie lautet die Gleichung die gelöst werden soll?

von Wolfgang (Gast)


Lesenswert?

Carol Z. schrieb:
> Wie kann man am besten in c++ solche Gleichungen iterativ lösen?

Was hat der Algorithmus mit der Programmiersprache zu tun?

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Erste Methode ist Newton-Raphson Iteration für ƒ(x) = g(x) - x:

1) Startwert für Iteration raten oder ausarbeiten

2) Iterieren bis zur gewünschten Genauigkeit:

* Funktioniert gut (quadratische Konvergenz) für einfache Nullstellen 
falls man die Iteration mit guter[tm] Näherung startet.

* Schlechtere Konvergenz (linear) bei mehrfacher Nullstelle.

* Es gibt Startwerte, für welche die Iteration nicht konvergiert, und 
diese können eine Menge von vollem Maß bilden.

von Carol Z. (Gast)


Lesenswert?

Rechenmonster schrieb:
> Wie lautet die Gleichung die gelöst werden soll?

g(x) = a * 1 / (1 - (1 + sqrt(1 / x))^-4)

also x - g(x) = 0

von Elektrofan (Gast)


Lesenswert?

Dann muss also schon mal x>0 sein.
Wie gross ist denn a?

von Hans W. (Firma: Wilhelm.Consulting) (hans-)


Lesenswert?

Entweder solver selber schreiben, oder z.b. boost oder eigen3 nehmen.

73

von Yalu X. (yalu) (Moderator)


Lesenswert?

Für a≠0 hat die Funktion keine reellen Nullstellen.

von M.A. S. (mse2)


Lesenswert?

Yalu X. schrieb:
> Für a≠0 hat die Funktion keine reellen Nullstellen.
Es geht nicht um die Nullstellen von g(x) sondern von x-g(x), da wird es 
schon Nullstelle(n) geben.

von Carol Z. (Gast)


Lesenswert?

Elektrofan schrieb:
> Dann muss also schon mal x>0 sein.
> Wie gross ist denn a?

a ist nicht 0 reel und konstant.

von Maxe (Gast)


Lesenswert?

Carol Z. schrieb:
> g(x) = a * 1 / (1 - (1 + sqrt(1 / x))^-4)
>
> also x - g(x) = 0

Das "also" macht hier keinen Sinn.
Bist du sicher dass g(x) = x ist?

von Carol Z. (Gast)


Lesenswert?

Maxe schrieb:
> Carol Z. schrieb:
>> g(x) = a * 1 / (1 - (1 + sqrt(1 / x))^-4)
>> also x - g(x) = 0
>
> Das "also" macht hier keinen Sinn.
> Bist du sicher dass g(x) = x ist?

Ja da bin ich mir sicher. Wie gesagt das ist das Optimierungsproblem für 
x, das es zu lösen gilt.

von Yalu X. (yalu) (Moderator)


Lesenswert?

> Yalu X. schrieb:
>> Für a≠0 hat die Funktion keine reellen Nullstellen.
> Es geht nicht um die Nullstellen von g(x) sondern von x-g(x), da wird es
> schon Nullstelle(n) geben.

Upps, das hatte ich übersehen. Ja du hast recht, dann gibt es natürlich
(mindestens) eine reelle Lösung.

Da die Funktion fest vorgegeben ist, kann man das mit Newton lösen,
allerdings ist dann die Festlegung des Startwerts nicht ganz trivial.
Dasselbe Problem hat man auch mit der Regula falsi.

Man kann die Gleichung aber auch in eine algebraische Gleichung in √x
umformen. Dafür gibt es Algorithmen, die ohne die Vorgabe eines
Startwerts sämtliche Lösungen liefern, bspw. den PolynomSolver in
eigen3/unsupported. Das sieht dann etwa so aus:

solve.cpp:
1
#include <iostream>
2
#include <cstdlib>
3
#include <eigen3/unsupported/Eigen/Polynomials>
4
5
int main(int argc, char *argv[]) {
6
  const int degree = 5;
7
  const double a = strtod(argv[1], NULL);
8
  Eigen::Vector<double, degree+1> coeffs(a, 4*a, 6*a-1, 4*a-4, a-6, -4);
9
  Eigen::PolynomialSolver<double, degree> solver;
10
  solver.compute(coeffs);
11
  const auto roots = solver.roots();
12
  for (auto c: roots) {
13
    const auto realpart = c.real();
14
    if (c.imag() == 0 && realpart > 0) {
15
      const auto solution = realpart * realpart;
16
      std::cout << solution << '\n';
17
    }
18
  }
19
}

Anwendungsbeispiel:
1
$ solve 4.2  # a = 4.2
2
5.54664

Gegenprobe:
1
4.2 * 1 / (1 - (1 + sqrt(1 / 5.54664))**-4) = 5.54664

Neben der Eigen-Bibliothek gibt es noch jede Menge anderer Bibliotheken,
die eine ähnliche Funktion bereitstellen. Am besten suchst du einfach
nach Polynomial Solver.

von Carol Z. (Gast)


Lesenswert?

Moment es geht darum nach x zu lösen nicht nach a. a ist nur ein 
konstanter Faktor.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Carol Z. schrieb:
> Moment es geht darum nach x zu lösen

Das hat Yalu doch gemacht? a = 4.2  =>  x ≈ 5.54664

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.