Hauptseite: Unterschied zwischen den Versionen

Aus MWiki
Wechseln zu: Navigation, Suche
(Intexverfahren)
(Hauptsätze der Analysis und Approximationssatz)
Zeile 1: Zeile 1:
 
__NOTOC__
 
__NOTOC__
 
= Willkommen bei MWiki =
 
= Willkommen bei MWiki =
−
== Satz des Monats ==
+
== Sätze des Monats ==
−
Das Intexverfahren löst die meisten lösbaren LPs mit <em>Int</em>er-/<em>Ex</em>trapolationen in <math>\mathcal{O}({\vartheta}^3)</math>.
+
=== Erster Hauptsatz der exakten Differential- und Integralrechnung für <abbr title="Kurvenintegral">KI</abbr>e ===
 +
Die Funktion <math>F(z)={\uparrow}_{\gamma }{f(\zeta ){\downarrow}\zeta }</math> ist mit <math>\gamma: [d, x[ \, \cap \, C \rightarrow A \subseteq {}^{(\omega)}\mathbb{K}, C \subseteq \mathbb{R}, f: A \rightarrow {}^{(\omega)}\mathbb{K}, d \in G = [a, b[ \, \cap \, C</math> bei Wahl von <math>{}^\curvearrowright \gamma(x) = \gamma({}^\curvearrowright x)</math> exakt differenzierbar und es gilt für alle <math>x \in G</math> und <math>z = \gamma(x)</math>
  
−
== Beweis und Algorithmus ==
 
−
Sei <math>z := 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, \rho], Ax - b \le r{\upharpoonright}_m, c - {A}^{T}y \le r{\upharpoonright}_n\}</math> habe den Radius <math>\rho := s|\min \; \{b_1, ..., b_m, -c_1, ..., -c_n\}|</math> und den Skalierungsfaktor <math>s \in [1, 2]</math>.
 
  
 +
<div style="text-align:center;"><math>F^{\prime}(z) = f(z).</math></div>
  
−
Es folgt <math>0{\upharpoonright}_z \in \partial P_{\rho}</math>. Nach dem starken Dualitätssatz löst das LP min <math>\{ r \in [0, \rho] : (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>. 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, \rho] : t \in {}^{\omega}\mathbb{R}_{&gt; 0}, t(x_0, y_0)^T \in P_r\}</math> approximiert <math>g</math> besser.
+
==== Beweis ====
 +
<math>{\downarrow}F(z)</math> <math>={\uparrow}_{t\in [d,x] \cap C}{f(\gamma (t)){{\gamma }^{\prime}}(t){\downarrow}t}-{\uparrow}_{t\in [d,x[ \, \cap \, C}{f(\gamma (t)){{\gamma }^{\prime}}(t){\downarrow}t}</math> <math>={\uparrow}_{x}{f(\gamma (t))\tfrac{\gamma ({}^\curvearrowright t)-\gamma (t)}{{}^\curvearrowright t-t}{\downarrow}t}</math> <math>=f(\gamma (x)){{\gamma}^{\prime}}(x){\downarrow}x=</math> <math>\,f(\gamma (x))({}^\curvearrowright\gamma (x)-\gamma (x))</math> <math>=f(z){\downarrow}z.\square</math>
  
 +
=== Zweiter Hauptsatz der exakten Differential- und Integralrechnung für <abbr title="Kurvenintegral">KI</abbr>e ===
 +
Mit <math>\gamma: G \rightarrow {}^{(\omega)}\mathbb{K}</math> gilt wie oben vorausgesetzt
  
−
Es wird <math>r \le \check{\rho}</math> erreicht und mit <math>t^o(x^o, y^o)^T</math> wiederholt, bis ggf. <math>g \in P_0</math> in <math>\mathcal{O}({}_2\rho^2dmn)</math> berechnet ist. 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 die Berechnung gestoppt, andernfalls wiederholt, bis min <math>r = 0</math> oder min <math>r &gt; 0</math> feststeht.<math>\square</math>
 
  
−
== Leseempfehlung ==
+
<div style="text-align:center;"><math>F(\gamma (b))-F(\gamma (a))={\uparrow}_{\gamma }{{F^{\prime}}(\zeta ){\downarrow}\zeta }.</math></div>
 +
 
 +
==== Beweis ====
 +
<math>F(\gamma (b))-F(\gamma (a))</math> <math>={+}_{t\in G}{F({}^\curvearrowright\,\gamma (t))}-F(\gamma (t))</math> <math>={+}_{t\in G}{{{F}^{\prime}}(\gamma (t))({}^\curvearrowright\,\gamma (t)-\gamma (t))}</math> <math>={\uparrow}_{t\in G}{{F^{\prime}}(\gamma (t)){{\gamma }^{\prime}}(t){\downarrow}t}</math> <math>={\uparrow}_{\gamma }{{F_{{}^\curvearrowright }^{\prime}}(\zeta ){\downarrow}\zeta }.\square</math>
 +
 
 +
=== Approximationssatz ===
 +
Die Ableitungen <math>f^{(s)}(x) \in {}^{\omega}\mathbb{R}</math> für <math>x \in {}^{\omega}\mathbb{R}</math> erlauben die interpolierende Funktion <math>g(x) := {+}_{r=0}^{\acute{m}}{\chi_{]x_r, x_{\grave{r}}[}(x)((x_{\grave{r}}-x)p_r(x)+(x-x_r)p_{\grave{r}}(x))/(x_{\grave{r}}-x_r)}+{+}_{r=0}^m{\chi_{\{x_r\}}(x)p_r(x)}</math> für <math>m, n \in {}^{\nu}\mathbb{N}</math> und <math>p_r(x) := {+}_{s=0}^n{f^{(s)}(x_r){(x-x_r)}^s/s!}</math> in <math>\mathcal{O}(\sigma mn)</math> zu berechnen, wobei <math>f^{(s)}(x_r) = g^{(s)}(x_r)</math> für alle <math>x_r \in {}^{\omega}\mathbb{R}</math> gilt. Im Komplexen ist <math>{}^{\omega}\mathbb{R}</math> durch <math>{}^{\omega}\mathbb{C}</math> zu ersetzen und es gelte <math>x = \gamma(t) \in {}^{\omega}\mathbb{C}</math> für den Weg <math>\gamma(t)</math> mit <math>t \in {}^{\omega}\mathbb{R}.\square</math>
 +
 
 +
== Leseempfehlungen ==
 
[https://de.calameo.com/books/00377797710a3d3e2cb97 Nichtstandardmathematik]
 
[https://de.calameo.com/books/00377797710a3d3e2cb97 Nichtstandardmathematik]
  
 
[[en:Main Page]]
 
[[en:Main Page]]

Version vom 1. Januar 2024, 13:38 Uhr

Willkommen bei MWiki

Sätze des Monats

Erster Hauptsatz der exakten Differential- und Integralrechnung für KIe

Die Funktion [math]\displaystyle{ F(z)={\uparrow}_{\gamma }{f(\zeta ){\downarrow}\zeta } }[/math] ist mit [math]\displaystyle{ \gamma: [d, x[ \, \cap \, C \rightarrow A \subseteq {}^{(\omega)}\mathbb{K}, C \subseteq \mathbb{R}, f: A \rightarrow {}^{(\omega)}\mathbb{K}, d \in G = [a, b[ \, \cap \, C }[/math] bei Wahl von [math]\displaystyle{ {}^\curvearrowright \gamma(x) = \gamma({}^\curvearrowright x) }[/math] exakt differenzierbar und es gilt für alle [math]\displaystyle{ x \in G }[/math] und [math]\displaystyle{ z = \gamma(x) }[/math]


[math]\displaystyle{ F^{\prime}(z) = f(z). }[/math]

Beweis

[math]\displaystyle{ {\downarrow}F(z) }[/math] [math]\displaystyle{ ={\uparrow}_{t\in [d,x] \cap C}{f(\gamma (t)){{\gamma }^{\prime}}(t){\downarrow}t}-{\uparrow}_{t\in [d,x[ \, \cap \, C}{f(\gamma (t)){{\gamma }^{\prime}}(t){\downarrow}t} }[/math] [math]\displaystyle{ ={\uparrow}_{x}{f(\gamma (t))\tfrac{\gamma ({}^\curvearrowright t)-\gamma (t)}{{}^\curvearrowright t-t}{\downarrow}t} }[/math] [math]\displaystyle{ =f(\gamma (x)){{\gamma}^{\prime}}(x){\downarrow}x= }[/math] [math]\displaystyle{ \,f(\gamma (x))({}^\curvearrowright\gamma (x)-\gamma (x)) }[/math] [math]\displaystyle{ =f(z){\downarrow}z.\square }[/math]

Zweiter Hauptsatz der exakten Differential- und Integralrechnung für KIe

Mit [math]\displaystyle{ \gamma: G \rightarrow {}^{(\omega)}\mathbb{K} }[/math] gilt wie oben vorausgesetzt


[math]\displaystyle{ F(\gamma (b))-F(\gamma (a))={\uparrow}_{\gamma }{{F^{\prime}}(\zeta ){\downarrow}\zeta }. }[/math]

Beweis

[math]\displaystyle{ F(\gamma (b))-F(\gamma (a)) }[/math] [math]\displaystyle{ ={+}_{t\in G}{F({}^\curvearrowright\,\gamma (t))}-F(\gamma (t)) }[/math] [math]\displaystyle{ ={+}_{t\in G}{{{F}^{\prime}}(\gamma (t))({}^\curvearrowright\,\gamma (t)-\gamma (t))} }[/math] [math]\displaystyle{ ={\uparrow}_{t\in G}{{F^{\prime}}(\gamma (t)){{\gamma }^{\prime}}(t){\downarrow}t} }[/math] [math]\displaystyle{ ={\uparrow}_{\gamma }{{F_{{}^\curvearrowright }^{\prime}}(\zeta ){\downarrow}\zeta }.\square }[/math]

Approximationssatz

Die Ableitungen [math]\displaystyle{ f^{(s)}(x) \in {}^{\omega}\mathbb{R} }[/math] für [math]\displaystyle{ x \in {}^{\omega}\mathbb{R} }[/math] erlauben die interpolierende Funktion [math]\displaystyle{ g(x) := {+}_{r=0}^{\acute{m}}{\chi_{]x_r, x_{\grave{r}}[}(x)((x_{\grave{r}}-x)p_r(x)+(x-x_r)p_{\grave{r}}(x))/(x_{\grave{r}}-x_r)}+{+}_{r=0}^m{\chi_{\{x_r\}}(x)p_r(x)} }[/math] für [math]\displaystyle{ m, n \in {}^{\nu}\mathbb{N} }[/math] und [math]\displaystyle{ p_r(x) := {+}_{s=0}^n{f^{(s)}(x_r){(x-x_r)}^s/s!} }[/math] in [math]\displaystyle{ \mathcal{O}(\sigma mn) }[/math] zu berechnen, wobei [math]\displaystyle{ f^{(s)}(x_r) = g^{(s)}(x_r) }[/math] für alle [math]\displaystyle{ x_r \in {}^{\omega}\mathbb{R} }[/math] gilt. Im Komplexen ist [math]\displaystyle{ {}^{\omega}\mathbb{R} }[/math] durch [math]\displaystyle{ {}^{\omega}\mathbb{C} }[/math] zu ersetzen und es gelte [math]\displaystyle{ x = \gamma(t) \in {}^{\omega}\mathbb{C} }[/math] für den Weg [math]\displaystyle{ \gamma(t) }[/math] mit [math]\displaystyle{ t \in {}^{\omega}\mathbb{R}.\square }[/math]

Leseempfehlungen

Nichtstandardmathematik

Abgerufen von „https://de.mwiki.de/index.php?title=Hauptseite&oldid=288“