Schranke Polynom < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:25 Mi 03.04.2013 | | Autor: | quasimo |
| Aufgabe | | Gegeben ein beliebiges Polynom p(x) = [mm] a_n x^n [/mm] + [mm] a_{n-1} x^{n-1} +..+a_1 [/mm] x + [mm] a_0 [/mm] mit ganzzahligen Koeffizienten [mm] a_0, a_1 [/mm] ,.., [mm] a_{n-1} \in \IZ [/mm] und gesucht ist eine ganze Zahl x [mm] \in \IZ, [/mm] sodass p(x)=0. Wenn nicht alle Koeffizienten 0 sind, dann hat die Aufgabe höchstens n Lösungen. Mann kann leicht eine obere Schranke für den Betrag einer Lösung des Problems angeben. Damit verbleiben nur noch endlich viele potenzielle Lösungen, die man alle ausprobieren kann. |
Servus.
Was ist gemeint mit der oberen Schranke? Die kann ich dich nicht allgemein für jedes Polynom angeben? Wie ist dass denn genau gemeint?
LG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:03 Mi 03.04.2013 | | Autor: | abakus |
> Gegeben ein beliebiges Polynom p(x) = [mm]a_n x^n[/mm] + [mm]a_{n-1} x^{n-1} +..+a_1[/mm]
> x + [mm]a_0[/mm] mit ganzzahligen Koeffizienten [mm]a_0, a_1[/mm] ,..,
> [mm]a_{n-1} \in \IZ[/mm] und gesucht ist eine ganze Zahl x [mm]\in \IZ,[/mm]
> sodass p(x)=0. Wenn nicht alle Koeffizienten 0 sind, dann
> hat die Aufgabe höchstens n Lösungen. Mann kann leicht
> eine obere Schranke für den Betrag einer Lösung des
> Problems angeben. Damit verbleiben nur noch endlich viele
> potenzielle Lösungen, die man alle ausprobieren kann.
> Servus.
> Was ist gemeint mit der oberen Schranke? Die kann ich dich
> nicht allgemein für jedes Polynom angeben? Wie ist dass
> denn genau gemeint?
>
> LG
Hallo,
ein Polynom n-ten Grades mit n Lösungen [mm] $x_1 \cdots x_n$ [/mm] lässt sich schreiben als [mm] $(x-x_1)*(x-x_2)*\cdots(x-x_n)$. [/mm] Wenn du das ausmultiplizierst, ist der Betrag des erhaltenen Absolutglied [mm] $a_n$ [/mm] der Betrag des Produkts aller Lösungen. Da die Lösungen ganzzahlig sind, ist der Betrag des Produkts nicht kleiner als der Betrag einer beliebigen Einzellösung (und eignet sich somit als Schranke).
(Dabei darf natürlich keine der Lösungen 0 sein).
Du musst jetzt allerdings noch darüber nachdenken, ob diese Überlegung auch anwendbar ist, wenn es weniger als n Lösungen gibt.
Gruß Abakus
EDIT: Ich bin vorschnell davon ausgegangen, dass der Faktor [mm] $a_n$ [/mm] den Wert 1 hat. Dass dies auch anders sein kann, muss bei der Faktorisierung berücksichtigt werden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:46 Do 18.04.2013 | | Autor: | felixf |
Moin!
> ein Polynom n-ten Grades mit n Lösungen [mm]x_1 \cdots x_n[/mm]
> lässt sich schreiben als [mm](x-x_1)*(x-x_2)*\cdots(x-x_n)[/mm].
> Wenn du das ausmultiplizierst, ist der Betrag des
> erhaltenen Absolutglied [mm]a_n[/mm] der Betrag des Produkts aller
> Lösungen. Da die Lösungen ganzzahlig sind, ist der Betrag
> des Produkts nicht kleiner als der Betrag einer beliebigen
> Einzellösung (und eignet sich somit als Schranke).
> (Dabei darf natürlich keine der Lösungen 0 sein).
> Du musst jetzt allerdings noch darüber nachdenken, ob
> diese Überlegung auch anwendbar ist, wenn es weniger als n
> Lösungen gibt.
Hier musst du davon ausgehen, dass alle Nullstellen ganzzahlig sind. Darauf kann man auch verzichten: wenn $f = [mm] \sum_{i=0}^n a_i X^i$ [/mm] ist mit [mm] $a_i \in \IZ$, $a_n \neq [/mm] 0$, und wenn $f(p/q) = 0$ ist mit teilerfremden Zahlen $p, q$, dann kann man zeigen, dass $p [mm] \mid a_0$ [/mm] und $q [mm] \mid a_n$ [/mm] ist.
Damit bekommt man nur recht wenige Kandidaten fuer rationale Loesungen und somit auch insb. fuer ganzzahlige Loesungen, ohne dass man irgendetwas ueber die Nullstellen voraussetzt.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:06 Do 04.04.2013 | | Autor: | fred97 |
> Gegeben ein beliebiges Polynom p(x) = [mm]a_n x^n[/mm] + [mm]a_{n-1} x^{n-1} +..+a_1[/mm]
> x + [mm]a_0[/mm] mit ganzzahligen Koeffizienten [mm]a_0, a_1[/mm] ,..,
> [mm]a_{n-1} \in \IZ[/mm] und gesucht ist eine ganze Zahl x [mm]\in \IZ,[/mm]
> sodass p(x)=0. Wenn nicht alle Koeffizienten 0 sind, dann
> hat die Aufgabe höchstens n Lösungen. Mann kann leicht
> eine obere Schranke für den Betrag einer Lösung des
> Problems angeben. Damit verbleiben nur noch endlich viele
> potenzielle Lösungen, die man alle ausprobieren kann.
> Servus.
> Was ist gemeint mit der oberen Schranke? Die kann ich dich
> nicht allgemein für jedes Polynom angeben? Wie ist dass
> denn genau gemeint?
Gesucht ist eine Zahl c>0 mit folgender Eigenschaft:
$ |x| [mm] \le [/mm] c$ für alle x [mm] \in \IZ [/mm] mit p(x)=0
Sei also x [mm] \in \IZ [/mm] und p(x)=0. Wir können von [mm] a_n \ne [/mm] 0 ausgehen.
Fall 1: x [mm] \ne [/mm] 0. Dann ist |x| [mm] \ge [/mm] 1, da x [mm] \in \IZ. [/mm] Somit ist [mm] \bruch{1}{|x|} \le [/mm] 1 und damit auch
(*) [mm] \bruch{1}{|x|^k} \le [/mm] 1 für k [mm] \in \{0,1,...,n\}
[/mm]
Aus [mm] a_nx^n=-(a_{n-1}x^{n-1}+...+a_1x+a_0) [/mm] folgt mit der Dreiecksungl.:
[mm] |a_n|*|x|^n \le |a_{n-1}|*|x^{n-1}|+...+|a_1|*|x|+|a_0|.
[/mm]
Wenn man durch [mm] |x^{n-1}| [/mm] dividiert, erhält man
[mm] |a_n|*|x| \le |a_{n-1}|+ \bruch{ |a_{n-2}|}{|x|}+...+\bruch{ |a_{1}|}{|x|^{n-2}}+\bruch{ |a_{0}|}{|x|^{n-1}}.
[/mm]
Ein Blick auf (*) zeigt dann:
[mm] |a_n|*|x| \le |a_{n-1}|+|a_{n-2}|+...+|a_{1}|+|a_{0}|.
[/mm]
Somit ist
(**) $|x| [mm] \le \bruch{|a_{n-1}|+|a_{n-2}|+...+|a_{1}|+|a_{0}|}{|a_n|}$
[/mm]
Wähle nun
[mm] $c:=\bruch{|a_{n-1}|+|a_{n-2}|+...+|a_{1}|+|a_{0}|}{|a_n|}$
[/mm]
Fall 2: x=0. In diesem Fall gilt die Ungleichung (**) trivialerweise.
Noch eine Bemerkung:
Nirgendwo habe ich benutzt, dass $ [mm] a_0, a_1 [/mm] $ ,.., $ [mm] a_{n-1} \in \IZ [/mm] $ gilt ! Dass x [mm] \in \IZ [/mm] ist, habe ich im Fall 1 auch nur gebraucht, um auf |x| [mm] \ge [/mm] 1 zu kommen.
Fazit:
Ist x [mm] \in \IR [/mm] und |x| [mm] \ge [/mm] 1 und p(x)=0, so gilt (**)
FRED
> LG
|
|
|
|
