Hauptseite: Unterschied zwischen den Versionen

Aus MWiki
Wechseln zu: Navigation, Suche
(Intexverfahren)
K (→‎Umkehrsatz für Taylorreihen)
(37 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
 
__NOTOC__
 
__NOTOC__
 
= Willkommen bei MWiki =
 
= Willkommen bei MWiki =
−
== Satz des Monats ==
+
== Sätze des Monats ==
−
Das Intexverfahren löst jedes lösbare LP in <math>\mathcal{O}({\vartheta}^3)</math>.
+
=== Anzahlsatz der algebraischen Zahlen ===
  
−
== Beweis und Algorithmus ==
+
Mit der Riemannschen Zetafunktion <math>\zeta</math> haben die algebraischen Zahlen vom Polynom- oder Reihengrad <math>m</math> und damit allgemein asymptotisch die Anzahl <math>\mathbb{A}(m, n) = \widetilde{\zeta(\grave{m})}\,z(m){{(2n+1)}^{m}}\left( n+\mathcal{O}({_e}n) \right)</math>, wobei <math>z(m)</math> die durchschnittliche Anzahl der Nullstellen eines Polynoms oder einer Reihe ist.
−
Beweis und Algorithmus: Sei <math>z := \grave{m} + n</math> und <math>d \in [0, 1]</math> die Dichte von <math>A</math>. Zuerst werden <math>{b}^{T}y - {c}^{T}x \le 0, Ax \le b</math> sowie <math>{A}^{T}y \ge c</math> normiert und skaliert. <math>P_r := \{(x, y)^T \in {}^{\omega}\mathbb{R}_{\ge 0}^{z} : {b}^{T}y - {c}^{T}x \le r \in [0, \breve{r}], Ax - b \le \underline{r}_m, c - {A}^{T}y \le \underline{r}_n\}</math> habe den Radius <math>\breve{r} := s|\min \; \{b_1, ..., b_m, -c_1, ..., -c_n\}|</math> und den Skalierungsfaktor <math>s \in [1, 2]</math>. Es folgt <math>\underline{0}_{z} \in \partial P_{\breve{r}}</math>. Nach dem starken Dualitätssatz löst das LP min <math>\{ r \in [0, \breve{r}] : (x, y)^T \in P_r\}</math> ebenso die LPs max <math>\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}</math> und min <math>\{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\}</math>.
 
  
 +
==== Beweis: ====
 +
Der Fall <math>m = 1</math> erfordert nach <ref name="Scheid">[[w:Harald Scheid|<span class="wikipedia">Scheid, Harald</span>]]: ''Zahlentheorie'' : 1. Aufl.; 1991; Bibliographisches Institut; Mannheim; ISBN 9783411148417, S. 323.</ref> den Korrekturterm <math>\mathcal{O}({_e}n n)</math> und gibt die Anzahl <math>4{+}_{k=1}^{n}{\varphi (k)}-1</math> der rationalen Zahlen über die eulersche <math>\varphi</math>-Funktion wieder. Für <math>m > 1</math> ändern die Teilbarkeitsverhältnisse weder den Korrekturterm <math>\mathcal{O}({_e}n n)</math> noch den Hauptterm. Polynome und Reihen mit <math>\text{ggT}({a}_{0}, {a}_{1}, \text{…} , {a}_{m}) \ne 1</math> werden durch <math>1/\zeta(\grave{m})</math> ausgeschlossen: Letzteres ergibt die Produktbildung über die Primzahlen <math>p</math> aller <math>(1 - {p}^{-\grave{m}})</math>, die hier Vielfache der <math>p</math> entfernen und Summen geometrischer Reihen sind.<math>\square</math>
  
−
Seine Lösung ist der geometrische Schwerpunkt <math>g</math> des Polytops <math>P_0</math>. Mit <math>p_k^* := \text{min}\,\check{p}_k + \text{max}\,\check{p}_k</math> für <math>k = 1, ..., \grave{z}</math> wird <math>g</math> durch <math>p_0 := (x_0, y_0, r_0)^T</math> approximiert, bis <math>||\Delta p||_1</math> hinreichend klein ist. Die Lösung <math>t^o(x^o, y^o, r^o)^T</math> des zweidimensionalen LPs min <math>\{ r \in [0, \check{r}] : t \in {}^{\omega}\mathbb{R}_{&gt; 0}, t(x_0, y_0)^T \in P_r\}</math> approximiert <math>g</math> besser und erreicht <math>r \le \hat{2}\breve{r}</math>. Dies wird mit <math>t^o(x^o, y^o)^T</math> wiederholt, bis ggf. <math>g \in P_0</math> in <math>\mathcal{O}({}_2\breve{r}^2dmn)</math> berechnet ist.
+
=== Satz von Brocard ===
 +
Es gilt <math>\{(m, n) \in {}^{\omega} \mathbb{N}^2 : n! + 1 = m^2\} = \{(5, 4), (11, 5), (71, 7)\}.</math>
  
 +
==== Beweis: ====
 +
Aus <math>n! = \acute{m}\grave{m}</math> folgt <math>m = \hat{r} \pm 1</math> für <math>r \in {}^{\omega} \mathbb{N}^{*}</math> und <math>n \ge 3</math>. Also ist <math>n! = \hat{r}(\hat{r}\pm2) = 8s(\hat{s} \pm 1)</math> mit <math>s \in {}^{\omega} \mathbb{N}^{*}</math>. Gelte <math>2^q \mid n!</math> und <math>2^{\grave{q}} \nmid n!</math> für maximales <math>q \in {}^{\omega} \mathbb{N}^{*}</math>. Damit ist <math>n! = 2^q(\hat{u} + 1)</math> für <math>u \in {}^{\omega} \mathbb{N}^{*}</math> und zwingend <math>n! = 2^q(2^{q-2} \pm 1)</math>. Die Primfaktorzerlegung von <math>n!</math> erfordert dann <math>n \le 7</math>, was die Behauptung ergibt.<math>\square</math>
  
−
Das Lösen aller zweidimensionalen LPs <math>\text{min}_k r_k</math> durch Bisektionsverfahren für <math>r_k \in {}^{\omega}\mathbb{R}_{\ge 0}</math> und <math>k = 1, ..., z</math> in jeweils <math>\mathcal{O}({\vartheta}^2)</math> ermittelt <math>q \in {}^{\omega}\mathbb{R}^k</math> mit <math>q_k := \Delta p_k \Delta r_k/r</math> und <math>r := \text{min}_k \Delta r_k</math>. Vereinfacht sei <math>|\Delta p_1| = … = |\Delta p_{z}|</math>. Hierbei wäre min <math>r_{\grave{z}}</math> für <math>p^* := p + wq</math> mit <math>w \in {}^{\omega}\mathbb{R}_{\ge 0}</math> ebenso zu lösen. Folgt <math>\text{min}_k \Delta r_k r = 0</math>, wird gestoppt, andernfalls wiederholt bis min <math>r = 0</math> oder min <math>r &gt; 0</math> feststeht.
+
=== Umkehrsatz für Taylorreihen ===
 +
Für <math>y \in f(\mathbb{D}), y(a) = b</math> und <math>y^{\prime}(a) \ne 0</math> ergibt der [[w:Lagrangesche_Inversionsformel#Formel_von_Lagrange-Bürmann|<span class="wikipedia">Satz von Bürmann</span>]]:<div style="text-align:center;"><math>f^{-1}(y) = a + \tilde{n} {\LARGE{\textbf{+}}}_{m=1}^n{\widetilde{m}{\tilde{\varepsilon}}^{\acute{m}}(y - b)^m({\tilde{u}}^{\acute{m}k})^T(f(\varepsilon u^k + a)^{-m})}+\mathcal{O}(\varepsilon^n).\square</math></div>
  
 
== Leseempfehlung ==
 
== Leseempfehlung ==
 +
 
[https://de.calameo.com/books/00377797710a3d3e2cb97 Nichtstandardmathematik]
 
[https://de.calameo.com/books/00377797710a3d3e2cb97 Nichtstandardmathematik]
 +
 +
== Einzelnachweise ==
 +
<references />
  
 
[[en:Main Page]]
 
[[en:Main Page]]

Version vom 18. Juli 2024, 00:21 Uhr

Willkommen bei MWiki

Sätze des Monats

Anzahlsatz der algebraischen Zahlen

Mit der Riemannschen Zetafunktion [math]\displaystyle{ \zeta }[/math] haben die algebraischen Zahlen vom Polynom- oder Reihengrad [math]\displaystyle{ m }[/math] und damit allgemein asymptotisch die Anzahl [math]\displaystyle{ \mathbb{A}(m, n) = \widetilde{\zeta(\grave{m})}\,z(m){{(2n+1)}^{m}}\left( n+\mathcal{O}({_e}n) \right) }[/math], wobei [math]\displaystyle{ z(m) }[/math] die durchschnittliche Anzahl der Nullstellen eines Polynoms oder einer Reihe ist.

Beweis:

Der Fall [math]\displaystyle{ m = 1 }[/math] erfordert nach [1] den Korrekturterm [math]\displaystyle{ \mathcal{O}({_e}n n) }[/math] und gibt die Anzahl [math]\displaystyle{ 4{+}_{k=1}^{n}{\varphi (k)}-1 }[/math] der rationalen Zahlen über die eulersche [math]\displaystyle{ \varphi }[/math]-Funktion wieder. Für [math]\displaystyle{ m \gt 1 }[/math] ändern die Teilbarkeitsverhältnisse weder den Korrekturterm [math]\displaystyle{ \mathcal{O}({_e}n n) }[/math] noch den Hauptterm. Polynome und Reihen mit [math]\displaystyle{ \text{ggT}({a}_{0}, {a}_{1}, \text{…} , {a}_{m}) \ne 1 }[/math] werden durch [math]\displaystyle{ 1/\zeta(\grave{m}) }[/math] ausgeschlossen: Letzteres ergibt die Produktbildung über die Primzahlen [math]\displaystyle{ p }[/math] aller [math]\displaystyle{ (1 - {p}^{-\grave{m}}) }[/math], die hier Vielfache der [math]\displaystyle{ p }[/math] entfernen und Summen geometrischer Reihen sind.[math]\displaystyle{ \square }[/math]

Satz von Brocard

Es gilt [math]\displaystyle{ \{(m, n) \in {}^{\omega} \mathbb{N}^2 : n! + 1 = m^2\} = \{(5, 4), (11, 5), (71, 7)\}. }[/math]

Beweis:

Aus [math]\displaystyle{ n! = \acute{m}\grave{m} }[/math] folgt [math]\displaystyle{ m = \hat{r} \pm 1 }[/math] für [math]\displaystyle{ r \in {}^{\omega} \mathbb{N}^{*} }[/math] und [math]\displaystyle{ n \ge 3 }[/math]. Also ist [math]\displaystyle{ n! = \hat{r}(\hat{r}\pm2) = 8s(\hat{s} \pm 1) }[/math] mit [math]\displaystyle{ s \in {}^{\omega} \mathbb{N}^{*} }[/math]. Gelte [math]\displaystyle{ 2^q \mid n! }[/math] und [math]\displaystyle{ 2^{\grave{q}} \nmid n! }[/math] für maximales [math]\displaystyle{ q \in {}^{\omega} \mathbb{N}^{*} }[/math]. Damit ist [math]\displaystyle{ n! = 2^q(\hat{u} + 1) }[/math] für [math]\displaystyle{ u \in {}^{\omega} \mathbb{N}^{*} }[/math] und zwingend [math]\displaystyle{ n! = 2^q(2^{q-2} \pm 1) }[/math]. Die Primfaktorzerlegung von [math]\displaystyle{ n! }[/math] erfordert dann [math]\displaystyle{ n \le 7 }[/math], was die Behauptung ergibt.[math]\displaystyle{ \square }[/math]

Umkehrsatz für Taylorreihen

Für [math]\displaystyle{ y \in f(\mathbb{D}), y(a) = b }[/math] und [math]\displaystyle{ y^{\prime}(a) \ne 0 }[/math] ergibt der Satz von Bürmann:

[math]\displaystyle{ f^{-1}(y) = a + \tilde{n} {\LARGE{\textbf{+}}}_{m=1}^n{\widetilde{m}{\tilde{\varepsilon}}^{\acute{m}}(y - b)^m({\tilde{u}}^{\acute{m}k})^T(f(\varepsilon u^k + a)^{-m})}+\mathcal{O}(\varepsilon^n).\square }[/math]

Leseempfehlung

Nichtstandardmathematik

Einzelnachweise

  1. ↑ Scheid, Harald: Zahlentheorie : 1. Aufl.; 1991; Bibliographisches Institut; Mannheim; ISBN 9783411148417, S. 323.
Abgerufen von „https://de.mwiki.de/index.php?title=Hauptseite&oldid=312“