Difference between revisions of "Main Page"

From MWiki
Jump to: navigation, search
m (Intex method)
(Fundamental theorems of calculus and approximation theorem)
Line 1: Line 1:
 
__NOTOC__
 
__NOTOC__
 
= Welcome to MWiki =
 
= Welcome to MWiki =
−
== Theorem of the month ==
+
== Theorems of the month ==
−
Intex methods solve almost every solvable LP with <em>int</em>er-/<em>ex</em>trapolations in <math>\mathcal{O}({\vartheta}^3)</math>.
+
=== First fundamental theorem of exact differential and integral calculus for <abbr title="line integral">LI</abbr>s ===
 +
The function <math>F(z)={\uparrow}_{\gamma }{f(\zeta ){\downarrow}\zeta }</math> where <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>, and choosing <math>{}^\curvearrowright \gamma(x) = \gamma({}^\curvearrowright x)</math> is exactly differentiable, and for all <math>x \in G</math> and <math>z = \gamma(x)</math>
  
−
== Proof and algorithm ==
 
−
Let <math>z := m + n</math> and <math>d \in [0, 1]</math> the density of <math>A</math>. First, normalise and scale <math>{b}^{T}y - {c}^{T}x \le 0, Ax \le b</math> as well as <math>{A}^{T}y \ge c</math>. Let <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,</math> <math>c - {A}^{T}y \le r{\upharpoonright}_n\}</math> have the radius <math>\rho := s|\min \; \{b_1, ..., b_m, -c_1, ..., -c_n\}|</math> and the scaling factor <math>s \in [1, 2]</math>.
 
  
 +
<div style="text-align:center;"><math>F^{\prime}(z) = f(z).</math></div>
  
−
It follows <math>0{\upharpoonright}_z \in \partial P_{\rho}</math>. By the strong duality theorem, LP min <math>\{ r \in [0, \rho] : (x, y)^T \in P_r\}</math> solves LPs max <math>\{{c}^{T}x : c \in {}^{\omega}\mathbb{R}^{n}, x \in {P}_{\ge 0}\}</math> and min <math>\{{b}^{T}y : y \in {}^{\omega}\mathbb{R}_{\ge 0}^{m}, {A}^{T}y \ge c\}</math>. Its solution is the geometric centre <math>g</math> of the polytope <math>P_0</math>. For <math>p_k^* := \text{min}\,\check{p}_k + \text{max}\,\check{p}_k</math> and <math>k = 1, ..., \grave{z}</math> approximate <math>g</math> by <math>p_0 := (x_0, y_0, r_0)^T</math> until <math>||\Delta p||_1</math> is sufficiently small. The solution <math>t^o(x^o, y^o, r^o)^T</math> of the two-dimensional LP min <math>\{ r \in [0, \rho] : t \in {}^{\omega}\mathbb{R}_{> 0}, t(x_0, y_0)^T \in P_r\}</math> approximates <math>g</math> better and achieves <math>r \le \check{\rho}</math>.
+
==== Proof ====
 +
<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>
  
 +
=== Second fundamental theorem of exact differential and integral calculus for <abbr title="line integral">LI</abbr>s ===
 +
Conditions above imply with <math>\gamma: G \rightarrow {}^{(\omega)}\mathbb{K}</math> that
  
−
Repeat this for <math>t^o(x^o, y^o)^T</math> until <math>g \in P_0</math> is computed in <math>\mathcal{O}({}_2\rho^2dmn)</math> if it exists. Solving all two-dimensional LPs <math>\text{min}_k r_k</math> by bisection methods for <math>r_k \in {}^{\omega}\mathbb{R}_{\ge 0}</math> and <math>k = 1, ..., z</math> in <math>\mathcal{O}({\vartheta}^2)</math> each time determines <math>q \in {}^{\omega}\mathbb{R}^k</math> where <math>q_k := \Delta p_k \Delta r_k/r</math> and <math>r := \text{min}_k \Delta r_k</math>. Let simplified <math>|\Delta p_1| = ... = |\Delta p_{z}|</math>. Here min <math>r_{\grave{z}}</math> for <math>p^* := p + wq</math> and <math>w \in {}^{\omega}\mathbb{R}_{\ge 0}</math> may be solved, too. If <math>\text{min}_k \Delta r_k r = 0</math> follows, stop computing, otherwise repeat until min <math>r = 0</math> or min <math>r &gt; 0</math> is sure.<math>\square</math>
+
 
 +
<div style="text-align:center;"><math>F(\gamma (b))-F(\gamma (a))={\uparrow}_{\gamma }{{F^{\prime}}(\zeta ){\downarrow}\zeta }.</math></div>
 +
 
 +
==== Proof ====
 +
<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>
 +
 
 +
=== Approximation theorem ===
 +
The derivatives <math>f^{(s)}(x) \in {}^{\omega}\mathbb{R}</math> for <math>x \in {}^{\omega}\mathbb{R}</math> allow computing the interpolating function <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> for <math>m, n \in {}^{\nu}\mathbb{N}</math> and <math>p_r(x) := {+}_{s=0}^n{f^{(s)}(x_r){(x-x_r)}^s/s!}</math> in <math>\mathcal{O}(\sigma mn)</math> where <math>f^{(s)}(x_r) = g^{(s)}(x_r)</math> holds for every <math>x_r \in {}^{\omega}\mathbb{R}</math>. Replace in the complex case <math>{}^{\omega}\mathbb{R}</math> by <math>{}^{\omega}\mathbb{C}</math> and put <math>x = \gamma(t) \in {}^{\omega}\mathbb{C}</math> for the path <math>\gamma(t)</math> where <math>t \in {}^{\omega}\mathbb{R}.\square</math>
  
 
== Recommended readings ==
 
== Recommended readings ==

Revision as of 12:50, 1 January 2024

Welcome to MWiki

Theorems of the month

First fundamental theorem of exact differential and integral calculus for LIs

The function [math]\displaystyle{ F(z)={\uparrow}_{\gamma }{f(\zeta ){\downarrow}\zeta } }[/math] where [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], and choosing [math]\displaystyle{ {}^\curvearrowright \gamma(x) = \gamma({}^\curvearrowright x) }[/math] is exactly differentiable, and for all [math]\displaystyle{ x \in G }[/math] and [math]\displaystyle{ z = \gamma(x) }[/math]


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

Proof

[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]

Second fundamental theorem of exact differential and integral calculus for LIs

Conditions above imply with [math]\displaystyle{ \gamma: G \rightarrow {}^{(\omega)}\mathbb{K} }[/math] that


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

Proof

[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]

Approximation theorem

The derivatives [math]\displaystyle{ f^{(s)}(x) \in {}^{\omega}\mathbb{R} }[/math] for [math]\displaystyle{ x \in {}^{\omega}\mathbb{R} }[/math] allow computing the interpolating function [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] for [math]\displaystyle{ m, n \in {}^{\nu}\mathbb{N} }[/math] and [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] where [math]\displaystyle{ f^{(s)}(x_r) = g^{(s)}(x_r) }[/math] holds for every [math]\displaystyle{ x_r \in {}^{\omega}\mathbb{R} }[/math]. Replace in the complex case [math]\displaystyle{ {}^{\omega}\mathbb{R} }[/math] by [math]\displaystyle{ {}^{\omega}\mathbb{C} }[/math] and put [math]\displaystyle{ x = \gamma(t) \in {}^{\omega}\mathbb{C} }[/math] for the path [math]\displaystyle{ \gamma(t) }[/math] where [math]\displaystyle{ t \in {}^{\omega}\mathbb{R}.\square }[/math]

Recommended readings

Nonstandard Mathematics

Retrieved from "https://en.mwiki.de/index.php?title=Main_Page&oldid=290"