アフィン演算

アフィン演算( AA ) は、自己検証型 数値解析のモデルです。AA では、対象となる数量は、データの不確実性の原因や計算中に行われた近似値を表す特定の基本変数のアフィン組み合わせ(アフィン形式) として表されます。

アフィン演算は、区間演算(IA)の改良を意図しており、一般化区間演算、一次テイラー演算、中心傾斜モデル、楕円体計算に似ています。つまり、一般公式の一次保証近似を自動的に導出する方法であるということです。

アフィン演算は、非線形方程式系の解決、動的システムの解析、関数の積分、微分方程式など、滑らかな関数への確実な囲みを必要とするあらゆる数値問題で潜在的に役立ちます。応用分野には、光線追跡、曲線のプロット、暗黙的およびパラメトリックな表面の交差、誤差解析（数学）、プロセス制御、電気回路の最悪ケース解析などがあります。

アフィン演算では、各入力または計算された量x は、既知の浮動小数点数と、値が [-1,+1] の範囲内にあることがわかっている記号変数 である式で表されます 。 ${\displaystyle x=x_{0}+x_{1}\epsilon _{1}+x_{2}\epsilon _{2}+{}}$${\displaystyle \cdots}$${\displaystyle {}+x_{n}\epsilon _{n}}$${\displaystyle x_{0},x_{1},x_{2},}$${\displaystyle \dots ,}$${\displaystyle x_{n}}$${\displaystyle \epsilon _{1},\epsilon _{2},\dots ,\epsilon _{n}}$

したがって、たとえば、範囲 [3,7] にあることがわかっている量X は、あるkに対してアフィン形式 で表すことができます。逆に、形式は、対応する量X が範囲 [3,17] にあることを意味します。 ${\displaystyle x=5+2\epsilon _{k}}$${\displaystyle x=10+2\epsilon _{3}-5\epsilon _{8}}$

2 つのアフィン形式 の間で記号が共有されている場合、 対応する量X、Y は、それらの結合範囲がそれらの個別範囲の直積よりも小さいという意味で、部分的に従属していることを意味します。たとえば、 およびの 場合、 XとYの個々の範囲は [2,18] と [13,27] ですが、ペア ( X、Y )の結合範囲は、角が (2,27)、(6,27)、(18,19)、(18,13)、(14,13)、(2,21) である六角形であり、これは長方形[2,18]×[13,27]の適切な部分集合です。 ${\displaystyle \epsilon_{j}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x=10+2\epsilon_{3}-6\epsilon_{8}}$${\displaystyle y=20+3\epsilon _{4}+4\epsilon _{8}}$

アフィン形式を標準の算術演算または基本関数と組み合わせて、式の確実な近似値を得ることができます。

たとえば、XとY のアフィン形式が与えられている場合、形式を加算するだけで、つまり、すべてのjに対して を設定することで、 Z = X + Yのアフィン形式を得ることができます。同様に、が既知の定数であるZ = Xのアフィン形式は、すべてのjに対して を設定することで計算できます。これは、 Z = X + Y +などの任意のアフィン演算に一般化されます。 ${\displaystyle x,y}$${\displaystyle z}$${\displaystyle z_{j}}$ ${\displaystyle \gets}$ ${\displaystyle x_{j}+y_{j}}$${\displaystyle z}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle z_{j}}$ ${\displaystyle \gets}$ ${\displaystyle \alpha x_{j}}$${\displaystyle \alpha}$${\displaystyle \beta}$${\displaystyle \gamma}$

乗算やのような非アフィン演算は、結果が のアフィン形式にならないため、正確には実行できません。その場合、およびによって示される範囲でF を1 次近似する適切なアフィン関数Gを取り、 を計算します。ここで、 はその範囲の絶対誤差の上限であり、 は 以前の形式では発生しない新しい記号変数です。 ${\displaystyle Z}$ ${\displaystyle \gets}$ ${\displaystyle F(X,Y,}$${\displaystyle \dots}$${\displaystyle )}$${\displaystyle Z}$ ${\displaystyle \gets}$ ${\displaystyle XY}$${\displaystyle Z}$ ${\displaystyle \gets}$ ${\displaystyle \sin(X)}$${\displaystyle \epsilon_{i}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$ ${\displaystyle \gets}$ ${\displaystyle G(x,y,}$${\displaystyle \dots}$${\displaystyle )+z_{k}\epsilon _{k}}$${\displaystyle z_{k}}$${\displaystyle |FG|}$${\displaystyle \epsilon_{k}}$

この形式は量Zの保証された囲みを与えます。さらに、アフィン形式は共同で点 ( X、Y、...、Z )の保証された囲みを提供します。これは多くの場合、個々の形式の範囲の直積よりもはるかに小さくなります。 ${\displaystyle z}$${\displaystyle x,y,}$${\displaystyle \dots}$${\displaystyle ,z}$

この方法を体系的に使用すると、入力と出力の間の一次相関を維持し、結合範囲の完全な囲みを保証しながら、与えられた量に対する任意の計算を、それらのアフィン形式に対する同等の計算に置き換えることができます。式内の各算術演算または基本関数呼び出しを、対応する AA ライブラリ ルーチンへの呼び出しに置き換えるだけです。

滑らかな関数の場合、各ステップで行われる近似誤差は、入力区間の幅hの 2 乗h ^{2に比例します。このため、アフィン演算では、誤差が}hに比例する標準区間演算よりもはるかに厳しい境界が得られることがよくあります。

確実に囲みを持たせるために、アフィン算術演算では、結果の係数 の計算で丸め誤差を考慮する必要があります。これは、各 を特定の方向に丸めることによって行うことはできません。そのような丸めを行うと、シンボル を共有するアフィン形式間の依存関係が偽になってしまうからです。代わりに、各 の丸め誤差の上限を計算し、そのすべてを新しいシンボルの係数に追加する必要があります(切り上げ)。したがって、丸め誤差があるため、Z = XやZ = X + Yなどのアフィン演算でも、余分な項 が追加されます。 ${\displaystyle z_{j}}$${\displaystyle z_{j}}$${\displaystyle \epsilon_{j}}$${\displaystyle \delta_{j}}$${\displaystyle z_{j}}$${\displaystyle \delta_{j}}$${\displaystyle z_{k}}$${\displaystyle \epsilon_{k}}$${\displaystyle \alpha}$${\displaystyle z_{k}\epsilon _{k}}$

丸め誤差の処理により、コードの複雑さと AA 操作の実行時間が増加します。これらの誤差が重要でないことが分かっているアプリケーションでは (入力データの不確実性や線形化誤差によって左右されるため)、丸め誤差制御を実装しない簡略化された AA ライブラリを使用できます。

アフィン演算は、次のように行列形式で表示できます。 を、計算中のある時点で使用されているすべての入力量と計算量とします。これらの量のアフィン形式は、単一の係数行列Aとベクトルbで表すことができます。ここで、要素はのアフィン形式における記号の係数であり、 はその形式の独立項です。すると、量の結合範囲、つまり点の範囲は、によって定義されるからへのアフィン写像によるハイパーキューブの像になります。 ${\displaystyle X_{1},X_{2},}$${\displaystyle \dots ,}$${\displaystyle X_{m}}$${\displaystyle A_{i,j}}$${\displaystyle \epsilon_{j}}$${\displaystyle X_{i}}$${\displaystyle b_{i}}$${\displaystyle (X_{1},X_{2},}$${\displaystyle \dots ,}$${\displaystyle X_{m})}$${\displaystyle U^{n}=[-1,+1]^{n}}$${\displaystyle U^{n}}$${\displaystyle R^{m}}$${\displaystyle \epsilon }$ ${\displaystyle \to}$ ${\displaystyle A\epsilon +b}$

このアフィン写像の値域は、量の結合範囲を囲むゾノトープです。したがって、AA は「ゾノトープ演算」であると言えます。AA の各ステップでは通常、行列Aに 1 行と 1 列が追加されます。 ${\displaystyle X_{1},X_{2},}$${\displaystyle \dots ,}$${\displaystyle X_{m}}$

通常、各 AA 演算は新しいシンボルを作成するため、アフィン形式の項の数は、計算に使用される演算の数に比例する可能性があります。したがって、2 つ以上のシンボルを新しいシンボルのより小さなセットに置き換える「シンボル凝縮」手順を適用する必要がよくあります。幾何学的には、これは複雑なゾノトープP を、それを囲むより単純なゾノトープQに置き換えることを意味します。この操作は、最終的なゾノトープの一次近似特性を破壊せずに実行できます。 ${\displaystyle \epsilon_{k}}$${\displaystyle \epsilon_{k}}$

アフィン演算は、上で説明したように、グローバル配列Aとグローバル ベクトルbによって実装できます。このアプローチは、計算する量のセットが小さく、事前にわかっている場合には十分です。このアプローチでは、プログラマーは行インデックスと関心のある量との対応を外部的に維持する必要があります。グローバル変数には、これまでに計算されたアフィン形式 (行) の数mと、これまでに使用されたシンボル (列) の数n が保持され、AA 操作ごとに自動的に更新されます。

あるいは、各アフィン形式を係数の個別のベクトルとして実装することもできます。このアプローチは、特に AA を内部的に使用する可能性のあるライブラリ プロシージャへの呼び出しがある場合に、プログラミングにとってより便利です。各アフィン形式には、ニーモニック名を付けることができます。この名前は、必要なときに割り当て、プロシージャに渡し、不要になったときに再利用できます。AA コードは、元の式に非常に近くなります。グローバル変数には、これまでに使用されたシンボルの数nが保持されます。

かなり長い計算では、「ライブ」量のセット（将来の計算で使用される）は、すべての計算された量のセットよりもはるかに小さくなります。また、「ライブ」シンボルのセットも同様です。この状況では、行列とベクトルの実装は時間とスペースを無駄にしすぎます。 ${\displaystyle \epsilon_{j}}$

このような状況では、スパース実装を使用する必要があります。つまり、各アフィン形式は、非ゼロ係数の項のみを含むペア (j, )のリストとして保存されます。効率を上げるために、項はjの順に並べ替える必要があります。この表現により、AA 操作が多少複雑になりますが、各操作のコストは、これまで使用されたシンボルの合計数ではなく、オペランドに現れる非ゼロ項の数に比例します。 ${\displaystyle x_{j}}$${\displaystyle x_{j}}$

これは LibAffa で使用される表現です。

• [1] AAに関するストルフィのページ。
• [2] LibAffa、アフィン演算のLGPL実装。
  • GitHubの libaffa
• [3] ASOLは、アフィン演算を用いて非線形方程式系のすべての解を見つける分岐枝刈り法である。
• [4] 2021-01-27にWayback Machineにアーカイブされました。YalAAは、アフィン演算（AA）用のオブジェクト指向C++ベースのテンプレートライブラリです。
• GitHubの kv (アフィン演算を使用できるC++ライブラリ)