1 Thema von osd

  • osd
  • Mitglied
  • Offline
  • Registrierungsdatum: 04-03-2002
  • Beiträge: 16

Thema: Polynomdivision

[ mod: hübscher gemacht  <img border="0" title="" alt="[Winken]" src="images/icons/wink.gif" />  ]
[ content belassen ]

---------------

es ist ein wenig kompliziert. es geht grundsätzlich um das berechnen der nullstellen einer funktion. da gibt es versch. möglichkeiten (je nach grad der funktion). oft ist es nötig, die sog. polynomdivision durchzuführen.

wir haben also zum beispiel die funktion
f(x) = x ^ 4 + 2x³ - 10x² - 6x + 45.
wir können so noch kein lösungsverfahren anwenden, wie zum beispiel äquivalentes umformen, lösungsformel, nullprodukt anwenden oder das substitutionsverfahren.

dem menschem fällt der nächste schritt leicht. wir müssen die funktion soweit umformen, dass sie für eines dieser lösungsverfahren anwendbar ist.
dazu suchen wir zuerst einen möglichen teiler von a0 (in diesem fall +45); diese wären also beispielsweise 5, -5, 3, -3, 9, -9 usw.
diese setzen wir nun nacheinander in die funktion ein und schauen, welcher teiler eine nullstelle ist. so kommen wir darauf, dass -3 eine nullstelle ist, weil f(-3) = 0.

diese nullstelle wenden wir nun in der polinomdivision an: folgendes wird gerechnet:
(x ^ 4 + 2x³ - 10x² - 6x + 45) / (x + 3).
schriftlich geht das ziemlich einfach auszurechnen. wir kommen auf
x³ - x² - 7x + 15!

jetzt können wir die weiteren nullstellen mit einem der lösungsverfahren ausrechnen. wie in etwa könnte sowas in einem c++ prgramm aussehen (oder irgendeine andere programmiersprache)? der pc muss ja erstma selber schauen, was teiler von a0 wären. dann muss er diesen nehmen, und in (x-teiler) einsetzen. durch das muss dann gerechnet werden, um auf unsere einfachere funktion zu kommen. ich hab schon einiges versucht, aber es nie wirklich hinbekommen. kann mir jemand helfen??!

andere funktionen wären zum beispiel noch:
f(x) = x³ + 2x² - 104x + 192
f(x) = x³ - 4x² - 16x + 15
f(x) = x³ + 2x² - 5x+6
f(x) = 4x³ - 19x² - 36x + 36
ihr könnt es ja mal ausprobieren.

eine kleine anmerkung noch von mir: das alles sollte bei jeder (polynomialen) funktion bis zum vierten grad funktionieren. die funktion f muss ganzrational sein und die form
f(x) = a4x ^ 4 + ... + a0 haben. sind dann alle koeffizienten a ganzzahlig  und a0 != 0, sollte es funktionieren. diese überprüfung müsste übrigens auch noch irgendwie in das programm rein   <img border="0" title="" alt="[Lächeln]" src="images/icons/smile.gif" />
 
  <small>[ 15-04-2002, 20:29: Beitrag editiert von: whitehouse ]</small>

visit OldSchoolDesign.de - part of Project LeChucky.de

osd's Webseite

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Polynomdivision

also, bitte mal konkret: was willst du zuerst? irgendwie kann ich nicht daraus ablesen, was du willst...

mfG whitehouse

3 Antwort von osd

  • osd
  • Mitglied
  • Offline
  • Registrierungsdatum: 04-03-2002
  • Beiträge: 16

Re: Polynomdivision

hallo. danke erstmal fürs hübscher machen  <img border="0" title="" alt="[Lächeln]" src="images/icons/smile.gif" />

also gut, jetzt mal ganz kurz und nacheinander:

1. wie kann ich teilnenner einer zahl herausfinden? beispielsweise von 45 -> 5, 9, 3 usw.?

2. also wie kann ich eine aufgabe wie (x ^ 4 + 2x³ - 10x² - 6x + 45) / (x + 3) ausrechnen, dass ich auf x³ - x² - 7x + 15 komme?

grü�e osd

visit OldSchoolDesign.de - part of Project LeChucky.de

osd's Webseite

4 Antwort von pao

  • pao
  • Mitglied
  • Offline
  • Registrierungsdatum: 12-07-2001
  • Beiträge: 199

Re: Polynomdivision

Also, mal ehrlich, ich habe nicht wirklich einen Schimmer, was Ihr da veranstaltet.
Nur bei dem Thema: wie finde ich einen Teilnenner, drängt sich mir auf, das hier ein Ergebnis ohne Nachkommastellen gefunden werden muss. Also "glattes Teilen". Und das erreiche ich in der Programmierung immer dadurch, dass ich abfrage, ob eine Modulo-Division das Ergebnis Null erbracht hat.
Wenn diese Idee hier gar nicht zutrifft:
Oh si tacuisses, philosophus manssisses.

pao's Webseite

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Polynomdivision

zu 1.: die einfachere methode ist (da nat. zahl, kannst ja auch mit abs und sgn ergänzen...), einfach zahl für zahl zu testen, ob (bsp. a=45 i=3)
a mod i = 0 => i teilt a... 
konkret pseudocode (T(n) ist die Menge der Teiler ns):
</font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr /><pre style="font-size:x-small; font-family: monospace;">for (i = 0; i < n; i++)
   if (a % i == 0)
     put(T(a), i);[/code]</blockquote><font size="2" face="Verdana, Helvetica, sans-serif">zu 2.: fangen wir lieber erst mal grundlegender an:
dich interessiert ein eindimensionales (mit einem Parameter) Polyonom p(x) etc., wobei du
r(x) = p(x) ~ q(x)
mit ~ als Operation festlegst. du möchtest nun r darstellen. seh ich das zunächst richtig?
ein polynom ist definiert durch seine koeffizienten
stellen wir es also einfach als feld (array) mit der Potenz als Index dar.
für
p(x) = 4 x^4 + 7 x^3 - 32x^2 + 64 - 7
ist also:
</font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr /><pre style="font-size:x-small; font-family: monospace;">Index        0  1   2 3 4
Koeffizient -7 64 -32 7 4[/code]</blockquote><font size="2" face="Verdana, Helvetica, sans-serif">soweit so gut... doch fragst du dich - was soll das?
so ist also die Polynomaddition zunächst ganz einfach:
r[i] = p[i] + q[i]
wobei der Name des Polynoms hier auch der Name des Feldes ist...
wieder als pseudocode:
  </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr /><pre style="font-size:x-small; font-family: monospace;">for (i = 0; i < max(n, k); i++)
   if (i >= k)
      r[i] = p[i];
   else if (i >= n)
      r[i] = q[i];
   else
      r[i] = p[i] + q[i];[/code]</blockquote><font size="2" face="Verdana, Helvetica, sans-serif">

mfG whitehouse
  • Herkunft: Mannheim
  • Registrierungsdatum: 17-04-2002
  • Beiträge: 11

Re: Polynomdivision

Hi osd, hi whitehouse,

das fing doch so gut an.

osd kommt mit einem groben Algorithmus für sein Problem, wieso artet das ganze in so einem Gestammel aus?

Naja, egal, irgendwann sind wir bei der Definition des Teilalgorithmus 'Teiler finden' angelangt:

  </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif"></font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Code:</font><hr /><pre style="font-size:x-small; font-family: monospace;"> for (i = 0; i < n; i++)  if (a % i == 0)    put(T(a), i);
  [/code]</blockquote><font size="2" face="Verdana, Helvetica, sans-serif"></font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">Für den ersten Wurf nicht schlecht, aber auch trivial.

Was mir direkt einfällt, ist das man den test gar nicht bis n durchführen muß, denn:
Bsp., Teiler von 6:
1 x 6 - 6 x 1
2 x 3 - 3 x 2
3 x 3 - 3 x 3

..., also reicht der test bis n/2 auf jeden fall aus. 1 und 6 sind auch nicht so interessant.

Was ich eigentlich sagen will ist, ihr seid doch medienkompetent, oder?  <img border="0" title="" alt="[Winken]" src="images/icons/wink.gif" /> 

osd, informier dich doch erstmal im Web und lass uns dann deine Probleme bei den gefundenen Algorithmen besprechen.

suche auf google nach Algorithmus Teiler ermitteln
suche auf google nach Algorithmus Polynomdivision

Gruß
Suani

7 Antwort von osd

  • osd
  • Mitglied
  • Offline
  • Registrierungsdatum: 04-03-2002
  • Beiträge: 16

Re: Polynomdivision

ok danke erstma an alle die sich zeit genommen haben.

den teilnenner einer zahl zu finden ist jetzt klar. das war aber auch nicht das primäre problem.

über polinomdivision werde ich mich erstmal (gemäÃ? suani) im netz informieren. die infos hier werden sicher auch hilfreich sein. sollten dann noch fragen auftreten, werd ich nochmal fragen  <img border="0" title="" alt="[Lächeln]" src="images/icons/smile.gif" />

visit OldSchoolDesign.de - part of Project LeChucky.de

osd's Webseite

  • Herkunft: Mannheim
  • Registrierungsdatum: 17-04-2002
  • Beiträge: 11

Re: Polynomdivision

Hi osd,

  </font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">Zitat:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif"> gemäß suani </font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">Ich hoffe du meinst gemäß Suanis Vorschlag und nicht gemäß Suanis Weisung.  <img border="0" title="" alt="[Breites Grinsen]" src="images/icons/grin.gif" /> 

Auch, wenn sich´s so anhört( aber ich denke der Ton gehört sich für ein Developer Forum), ich will euch keine Methodik aufzwingen, sondern mache nur Vorschläge.

Aber ich denke ihr habt das auch in diesem Sinne verstanden.

Gruß
Suani

9 Antwort von osd

  • osd
  • Mitglied
  • Offline
  • Registrierungsdatum: 04-03-2002
  • Beiträge: 16

Re: Polynomdivision

Natürlich meinte ich das - jetzt ohne Ironie und voller Ernst !!

Viel Spass OSD

visit OldSchoolDesign.de - part of Project LeChucky.de

osd's Webseite

10 Antwort von osd

  • osd
  • Mitglied
  • Offline
  • Registrierungsdatum: 04-03-2002
  • Beiträge: 16

Re: Polynomdivision

jetzt mal bitte ganz konkret. ich möchte die funktion f(x)=x^4 + 2x^3 - 10x^2 -6x + 45 mit g(x)=x+3 dividieren. zeigt mir doch bitte mal einen weg, dass ich auf q(x)=x^3 - x^2 - 7x + 15 komme.

wie kann ich also eine division durchführen, die der schriftlichen division nahekommt (beispiel auf http://ig.cs.tu-berlin.de/~gymstegl/mat … ly_div.htm ). sonst gab es bei google leider kein algorithmus, der mir weitergeholfen hat.

visit OldSchoolDesign.de - part of Project LeChucky.de

osd's Webseite

  • Herkunft: D-BaWü Ulm
  • Registrierungsdatum: 21-03-2001
  • Beiträge: 1.727

Re: Polynomdivision

doch, du hast einen gesehen, der dir weitergeholfen hat - du weißt es nur noch nich *g*. ich schau mal nach multiplikation - vielleicht find ich was...

mfG whitehouse

12 Antwort von matho

  • matho
  • Moderator
  • Offline
  • Herkunft: Deutschland
  • Registrierungsdatum: 21-01-2001
  • Beiträge: 1.352

Re: Polynomdivision

@ osd

Ich hatte bisher nicht geantwortet, weil ich zugegebenermaßen Dein
Problem nicht verstanden hatte. Es ist mir bis jetzt nicht ganz klar.
Aber vielleicht hilft Dir das:

Wenn Du die Nullstellen ermittelt hast, ergibt sich die Division
doch von selbst:

a*x^4 + b*x^3 + c*x^2 + d*x +e / x+n          ;               a=1;

=

x^3 + (b - a*n)*x^2 + (c - b*n + a*n^2)*x + (d - c*n + b*n^2 - a*n^3)

wobei der letzte Term gleich e/n ist.

Konkret:

(x^4 + 2x^3 - 10x^2 -6x + 45) / (x + 3)

also:  a=1, b=2, c=-10, d=-6, e=45, n=3

==> x^3 - x^2 - 7*x + 15

Ich weiß gar nicht recht, ob man das nun einen Algorithmus nennen
soll - naja, eventuell das Vorgehn (zunächst Nullstelle suchen, dann
Umformen....)

Hier ist mal ein kleines Beispiel in javascript (auf die Schnelle,
ich hatte momentan keine Zeit, es genauer zu machen), natürlich
nur mit Ganzzahlen:

<html>
<head>
<title></title>
<script>
var d=document,K=[],X=[],Z=['Nullstelle bei ','Nullstellen bei ','Keine ganzzahlige Nullstelle'];
function A(a){d.getElementsByTagName('div')[0].innerHTML=a};
function P(p1,p2){return Math.pow(p1,p2)};
function M(m){return X[0]!=0?Math.ceil(Math.abs(m/2)):100};
function T(t){return t.toString().match(/-/)?' '+t:' +'+t};

function N()
{r=/(^s*-?d+s*$)/;r0=/^s*$/;
  for(i=0;i<=4;i++)
  {X[i]=d.F.X[4-i].value.match(r)?d.F.X[4-i].value*1:d.F.X[4-i].value.match(r0)?0:'cucumber';
   if(typeof X[i]!='number'){alert('wreally rongg');break}
  };

x=-M(X[0]);

{while(x<M(X[0]))
  {x++;
   if(X[4]*P(x,4)+X[3]*P(x,3)+X[2]*P(x,2)+X[1]*P(x,1)+X[0]==0)K.push(x);
   A(K.length==1?Z[0]+K:K.length>1?Z[1]+K:Z[2]);
  };
};

for(i=0;i<K.length;i++)
  {K[i]=-K[i];
   k3=X[4]!=0?T(X[4])+'*x³ ':'';
   k2=X[4]!=0||X[3]!=0?T(X[3]-X[4]*K[i])+'*x² ':'';
   k1=X[4]!=0||X[3]!=0||X[2]!=0?T(X[2]-X[3]*K[i]+X[4]*P(K[i],2))+'*x ':'';
   k0=X[0]!=0?T(X[0]/K[i]):'';
   n=T(K[i]);
   if(n!=0)alert('/(x'+n+') =nn'+k3+k2+k1+k0);
  };

x=-M(X[0]);
K=[];
};
</script>
</head>
<body>
<form name=F>
<input type=text name=X size=3 value=1></input>* x^4 +
<input type=text name=X size=3 value=2></input>* x^3 +
<input type=text name=X size=3 value=-10></input>* x^2 +
<input type=text name=X size=3 value=-6></input>* x^1 +
<input type=text name=X size=3 value=45></input>
<input type=button value=R onclick='N()'></input>
</form>
<div></div>
</body>
</html>

Ein guter Rat vielleicht noch: wenn Du an sowas
arbeitest, gibt acht auf Fließkommazahlen, bzw.
etwaige 'Rundungsfehler' (aus menschlicher Sicht).

gruß

matho
 
  <small>[ 04-05-2002, 12:29: Beitrag editiert von: matho ]</small>

13 Antwort von Gero

  • Gero
  • Mitglied
  • Offline
  • Herkunft: Dortmund
  • Registrierungsdatum: 14-09-2000
  • Beiträge: 1.398

Re: Polynomdivision

Hi

Eine Frage:
Wenn du schon nen Computer hast, warum lässt du den nicht einfach stupide rackern und mit dem Newton-Verfahren oder einem ähnlichen eine Nullstelle annähren? Wenn man das in genügend Schritten macht ist die Nährung sowieso genau genug.
z.B. lässt du den PC die Funktion nach einer �nderung des Vorzeichens prüfen, an einer solche Stelle wird eine Tangente angelegt. An der Stelle wo diese Tangente die X-Achse schneidet wird wieder am Graphen eine Tangente angelegt usw. so nähert man sich der Nullstelle bei beliebig vielen Schritten beliebig genau an.
Klingt vielleicht kompiziert, ist aber die Methode, die ich als geläfige Art kennen gelernt hab zur Funktionsdisskusion mit einem Computer.
Frag mich jetzt nur nicht, wie man mit dem PC Ableiten kann  <img border="0" title="" alt="[Lächeln]" src="images/icons/smile.gif" />

Die Beschreibung, die ich mal hatte zur Kurvendisskussion hab ich leider nicht mehr  <img border="0" title="" alt="[Enttäscht]" src="images/icons/frown.gif" />

Gero's Webseite

14 Antwort von osd

  • osd
  • Mitglied
  • Offline
  • Registrierungsdatum: 04-03-2002
  • Beiträge: 16

Re: Polynomdivision

also ich muss ma sagen - danke an alle, die geantwortet haben. matho, du hast mir wirklich geholfen!

und als info für gero: mir ging es hier eigentlich mehr um die polinomdivision an sich, als um die ermittlung von nullstellen. bisektionsverfahren o.ä. und die umsetzung für 'n pc sind mir durchaus geläufig. trotzdem danke.

viel spass. osd.

visit OldSchoolDesign.de - part of Project LeChucky.de

osd's Webseite