Iterative Lösung nichtlinearer gleichungen

[Carol Z. (Gast)]

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?

[Johann L. (gjlayde)]

Nix genaues weiß man nicht.

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

[Carol Z. (Gast)]

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.

[Maxe (Gast)]

Reicht eine Lösung?

Newton-Verfahren?

[Elektrofan (Gast)]

Regula falsi?

[Rechenmonster (Gast)]

Wie lautet die Gleichung die gelöst werden soll?

[Wolfgang (Gast)]

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

Was hat der Algorithmus mit der Programmiersprache zu tun?

[Johann L. (gjlayde)]

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:

$$x\mapsto x-\frac{f(x)}{f'(x)} = x-\frac{g(x)-x}{g'(x)-1} = \frac{xg'(x)-g(x)}{g'(x)-1}$$

* 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.

[Carol Z. (Gast)]

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

[Elektrofan (Gast)]

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

[Hans W. (Firma: Wilhelm.Consulting) (hans-)]

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

73

[Yalu X. (yalu) (Moderator)]

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

[M.A. S. (mse2)]

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.

[Carol Z. (Gast)]

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

a ist nicht 0 reel und konstant.

[Maxe (Gast)]

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?

[Carol Z. (Gast)]

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.

[Yalu X. (yalu) (Moderator)]

> 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:

#include <iostream>
#include <cstdlib>
#include <eigen3/unsupported/Eigen/Polynomials>

int main(int argc, char *argv[]) {
  const int degree = 5;
  const double a = strtod(argv[1], NULL);
  Eigen::Vector<double, degree+1> coeffs(a, 4*a, 6*a-1, 4*a-4, a-6, -4);
  Eigen::PolynomialSolver<double, degree> solver;
  solver.compute(coeffs);
  const auto roots = solver.roots();
  for (auto c: roots) {
    const auto realpart = c.real();
    if (c.imag() == 0 && realpart > 0) {
      const auto solution = realpart * realpart;
      std::cout << solution << '\n';
    }
  }
}

Anwendungsbeispiel:

$ solve 4.2  # a = 4.2
5.54664

Gegenprobe:

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.

[Carol Z. (Gast)]

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

[Johann L. (gjlayde)]

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

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