Polynomdarstellung + Nullstellen

x2 · Hält's aus hier Beiträge: 3

Guten Tag die Herrschaften,

seit einiger Zeit muss ich mit der Aufgabe beschäftigen, die da heißt:

Ich solle eine Methode finden, um die Nullstellen zu berechnen...
Da gäbe es ja zwei Ansätze: das Newtonsche Verfahren und dann das Verfahren der Annäherung (genauer Name ist mir gerade entfallen)

Ich habe ein bißchen im Internet gesucht, gefunden, eingefügt und siehe da es "geht" aber leider nur bedingt.
Denn wenn ich Werte eingebe, die dem Programm nicht "passen" bleibt es entweder hängen (also endlosschleife) oder es gibt keine Nullstellen (also eig. gibt es eine er zeigt sie nur nicht an), zeichnet aber die Fkt.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

function f(x:real):real; // liefert den Funktionswert
begin
f:=k5*power(x,5)+k4*power(x,4)+k3*power(x,3)+k2*power(x,2)+k1*x+k0;
end;
procedure TPlotter.GetNull;
var x0,x1,x2:real;
begin
x0:= -100;
x1:=  100;
repeat
x2:= x1-f(x1)*(x1-x0)/(f(x1)-f(x0));
x0:=x1; //die Werte wechseln die Rollen
x1:=x2;
until abs(f(x2))<0.0000001 ;// Abbruchbedungung
Memo1.Lines.Add(FloatToStr(x2));
end;

woran kann das liegen?
Ist irgendwo ein Fehler drin?

Moderiert von Christian S.: Quote- durch Delphi-Tags ersetzt

Billi Berserker · Beiträge: 44

Du hast eine Funktion welche durch ein Polynom 5ten Grades dargestellt wird. Das Problem was du ganz einfach hast ist das es mehr als eine Nullstelle geben kann. Die üblichen Verfahren wie Newton benötigen alle einen Startwert und im Normallfall liefert dir das ganze nur eine der Nullstellen (welche Nullstelle hängt vom Startwert ab).

Es gibt haufenweise Verfahren wie man die Nullstellen bestimmten kann, oftmals ist jedes Verfahren jedoch für unterschiedliche Fälle am besten geeignet (Stetigkeit der Funktion? Anzahl der Nullstellen? Grenzwertverhalten?). Um wirklich alle Nullstellen zu bekommen kann es nötig sein einfach mehrere Verfahren zu kombinieren...

Am besten sollte man aber nicht einfach irgendwo ein Verfahren kopieren sondern sich selbst etwas Ausdenken was zu dem gegebenen Problem paßt.

Für ein Polynom mit halbwegs freundlichen Parametern würde ich o.B.d.A einfach mal annehmen das die Nullstellen gutartig sind und nicht gerade zu dicht aufeinander hocken. Also als erstes dein Intervall was untersucht werden soll in N gleich große Teilintervalle zerhacken und die Funktionswerte der linken und rechten Intervallgrenzen der N Teilintervalle berechnen. Ist (f(xi) < 0 und f(xi+1) > 0) oder (f(xi) > 0 und f(xi+1) < 0) steckt in diesem Teilintervall eine Nullstelle. Damit findest du also die Teilintervalle in denen sich eine Nullstelle befindet. Zur berechnung der Nullstelle aus den einzelnen Teilintervallen welche eine Nullstelle enthalten kannst du dann jedes beliebige Verfahren benutzen (oder dir selbst etwas ausdenken

)

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Ich nehme an, dass du das Sekantenverfahren oder Bisektionsverfahren implementieren musst. Damit findest du zwar nicht garantiert Nullstellen und schon gar nicht alle auf einmal, aber andere Verfahren sind da einiges komplizierter zu verstehen und implementieren.

Hier mal etwas Pseudocode für das Sekantenverfahren. Zwei Startwerte x0 und x1 müssen festgelegt werden.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

n = 0
tol = 1e-10 // Residuum
while abs(x1-x0) > tol
 temp=x1
 x1=x1-(x1-x0)/(f(x1)-f(x0))*f(x1)
 x0=temp
 n=n+1
end
x=x1 // Lösung

Folgendes sei trotzdem noch erwähnt: Um Nullstellen von beliebigen Polynomen numerisch geschickt zu berechnen stellt man normalerweise die Companion-Matrix zum zugehörigen Polynom auf und diagonalisiert diesen (Eigenwerte berechnen).

x2 · Hält's aus hier Beiträge: 3

ok danke,
ich werde mal heute gucken, ob ich eine Lösung finde, die der Aufgabe gerecht wird..

wenn ich was sinnvolles zu stande kriege, werde ich es posten ^^

----EDIT----
so ich habe dann doch was gefunden ^^

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

function f(x:real):real; // liefert den Funktionswert
begin
f :=k5*x*x*x*x*x + k4*x*x*x*x + k3*x*x*x + k2*x*x + k1*x + k0;
end;

function fs(x:real):real; // f'
    const h = 1E-12 ;
begin
fs := (f(x+h) - f(x - h)) / (2*h)
end;

function newton(x:Real):Real;
    const eps = 1E-12 ;
begin
  repeat
    x := x - f(x) / fs(x);
    until
    abs(f(x)) < eps;
    newton := x;
end;

procedure TPlotter.GetNull;
var    x:Real;
begin
x := - 40 ;
while x < 40 do begin
  if  f(x) * f(x + 0.1) <= 0 then
    memo1.Lines.add(floattostr(newton(x)));
  x := x + 0.1
  end;
end;

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme