(57)【要約】【課題】システムのモデル予測制御（ＭＰＣ）の方法が、ロケーションのマップにおいて有意であると識別されたロケーションにおいてのみ近似的な係数行列のエントリーを求める。【解決手段】ロケーションのマップは、近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別する。エントリーは、近似的な係数関数および正確な係数関数のうちの一方またはそれらの組み合わせを用いて求められる。次に、本方法は、近似的な係数行列を用いてプリコンディショナーを求め、このプリコンディショナーを有する反復方法を用いて、制御の現在の時間ステップにおける正確な係数関数によって定義された係数行列を有するＭＰＣの行列方程式を解くことによって、解ベクトルを求める。本方法は、解ベクトルを用いてシステムを制御する制御信号を生成する。【選択図】図１
2017084343.tif 000002
【特許請求の範囲】
【請求項１】
システムのモデル予測制御（ＭＰＣ）の方法であって、
ロケーションのマップにおいて有意であると識別されたロケーションにおいてのみ近似的な係数行列のエントリーをオンラインで求めるステップであって、前記エントリーは、前記ＭＰＣの正確な係数行列を近似するように求められ、前記ロケーションのマップは、前記近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別する、エントリーをオンラインで求めるステップと、
前記近似的な係数行列を用いて、エントリーをオンラインでプリコンディショナー行列の少なくとも一部分をオンラインで求めるステップであって、前記プリコンディショナー行列は、スパースであり、ブロック対角行列と異なるとともにブロック三角対角行列と異なる、プリコンディショナー行列を求めるステップと、
前記プリコンディショナー行列を有する反復方法を用いて、前記正確な係数行列を有する前記ＭＰＣの行列方程式を解くことによってオンラインで解ベクトルを求めるステップと、
前記解ベクトルを用いて前記システムをリアルタイムで制御する制御信号をオンラインで生成するステップと
を含み、該方法のステップは、少なくとも１つのプロセッサによって実行される、方法。
【請求項２】
前記有意なロケーションのマップをオフラインで求めるステップであって、該ロケーションのマップを、前記プロセッサに作動接続されたメモリに記憶する、マップをオフラインで求めるステップをさらに含み、
有意でないとしてマッピングされたロケーションは、前記プリコンディショナー行列内の前記ロケーションにおける前記近似的な係数行列のエントリーを無効にすることが、前記プリコンディショナー行列を有する前記反復方法の収束速度を所定の第１の閾値よりも大きく維持するか否かを調べることによる解析的導出および数値シミュレーションのうちの一方またはそれらの組み合わせによって求められる、請求項１に記載の方法。
【請求項３】
前記有意なロケーションのマップをオフラインで求めるステップであって、該ロケーションのマップを、前記プロセッサに作動接続されたメモリに記憶する、マップをオフラインで求めるステップをさらに含み、
前記有意なロケーションは、前記近似的な係数行列の絶対値エントリーによる最も大きなもののロケーションとして求められ、前記ロケーションのマップによって有意であると識別された非ゼロのエントリーの数は、前記近似的な係数行列のエントリーの総数の所定の割合および前記近似的な係数行列の前記有意なエントリーの絶対値未満の境界を定める所定の第２の閾値のうちの一方またはそれらの組み合わせによって求められる、請求項１に記載の方法。
【請求項４】
前記プリコンディショナー行列は、ブロック行列として求められ、各ブロックは、ブロック対角行列と低ランク行列との和として求められ、前記ブロックの前記ロケーションおよびサイズは、オフラインで求められる、請求項１に記載の方法。
【請求項５】
近似的な係数関数および正確な係数関数を求めるステップであって、ベクトルに適用される前記近似的な係数関数は、前記正確な係数関数を前記ベクトルに適用した結果を近似するものであり、前記ベクトルに適用される前記近似的な係数関数は、前記近似的な係数行列と前記ベクトルとの積を返し、前記ベクトルに適用される前記正確な係数関数は、前記正確な係数行列と前記ベクトルとの積を返す、近似的な係数関数および正確な係数関数を求めるステップと、
前記近似的な係数関数および前記正確な係数関数のうちの一方またはそれらの組み合わせを用いて、前記近似的な係数行列の前記エントリーをオンラインで更新するステップと
をさらに含む、請求項１に記載の方法。
【請求項６】
前記正確な係数行列を求める算術の精度よりも低い精度を有する算術を用いて、前記近似的な係数行列を求めるステップ
をさらに含む、請求項１に記載の方法。
【請求項７】
前記正確な係数行列内のエントリーの少なくとも１つのブロックの近似的な削除を用いて前記近似的な係数行列を求めるステップ
をさらに含む、請求項１に記載の方法。
【請求項８】
前記システムのモデルを用いて前記正確な係数行列を求めるステップと、
前記システムの前記モデルを近似するステップと、
前記システムの前記近似的なモデルを用いて前記近似的な係数行列を求めるステップと
をさらに含む、請求項１に記載の方法。
【請求項９】
前記近似的な係数行列は、前記制御の異なる時間ステップについて求められた前記正確な係数行列である、請求項１に記載の方法。
【請求項１０】
前記解くことは、メイン制御ルーチンの間にコントローラープロセッサによって実行され、前記方法は、
少なくとも１つの追加のプロセッサを用いて前記メイン制御ルーチンと並列に、前記近似的な係数行列、前記プリコンディショナー行列、および前記プリコンディショナー行列の因数分解のうちの１つまたはそれらの組み合わせを求めるステップ
をさらに含む、請求項１に記載の方法。
【請求項１１】
前記ＭＰＣは、前進差分ニュートン−クリロフ前処理付き反復方法によって前記ＭＰＣの必要な最適性条件を近似的に解く継続ＭＰＣである、請求項１に記載の方法。
【請求項１２】
前記プリコンディショナー行列を求めるステップは、
前記近似的な係数行列の行および列を並べ替えて、前記プリコンディショナー行列を生成することを含み、前記並べ替えのパターンは、前記プリコンディショナー行列の因数分解のメモリ使用量およびコストを最小にする前記行および前記列の順序付けを行うようにオフラインで求められる、請求項１に記載の方法。
【請求項１３】
因数分解方法を用いて前記プリコンディショナー行列をオンラインで因数分解するステップをさらに含み、前記因数分解は、
上下因数分解、下対角下転置因数分解、シュ−ル因数分解、コレスキー因数分解、直交上側因数分解、および反三角因数分解、極分解、固有値分解および特異値分解、並びにそれらのブロックバージョンのうちの１つまたはそれらの組み合わせを含む、請求項１に記載の方法。
【請求項１４】
前記反復方法は、
前処理付き定常方法、前処理付きクリロフ部分空間方法、前処理付き最小残差方法、前処理付き一般化最小残差方法、前処理付き勾配方法、前処理付きチェビシェフ方法、および前処理付きネステロフ方法のうちの１つまたはそれらの組み合わせを含む、請求項１に記載の方法。
【請求項１５】
前記プリコンディショナー行列を求めるステップは、
前記プリコンディショナー行列を対称正定値行列として求めることを含み、前記反復方法は前処理付き最小残差方法である、請求項１に記載の方法。
【請求項１６】
前記反復方法の収束の速度を求めるステップと、
前記収束の速度が閾値未満である場合、前記プリコンディショナー行列を更新するステップと
をさらに含む、請求項１に記載の方法。
【請求項１７】
プリコンディショナー関数を用いて前記反復方法を求めるステップをさらに含み、ベクトルに適用される前記プリコンディショナー関数は、前記プリコンディショナー行列の逆行列と前記ベクトルとの積を近似するものである、請求項１に記載の方法。
【請求項１８】
現在の時間ステップの前記反復方法の実行の間に前記プリコンディショナー行列を少なくとも部分的に更新するステップをさらに含み、前記反復方法は、前記プリコンディショナー行列が可変のプリコンディショナー行列であるように、前記プリコンディショナー行列の更新と同期して再開されるかまたは柔軟な反復方法である、請求項１に記載の方法。
【請求項１９】
前記解ベクトルを求めるステップは、
前記制御の以前の時間ステップから前記反復方法の反復を再開することなく、前記制御の現在の時間ステップにおいて、前記反復方法における前記行列方程式を更新することを含み、前記反復方法は、前記行列方程式が可変の行列方程式であるように柔軟な反復方法である、請求項１に記載の方法。
【請求項２０】
各時間ステップにおいて生成された制御信号に従ってシステムを制御するモデル予測コントローラーであって、
前記システムのモデルと、近似的な係数行列および正確な係数行列と、前記近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別するロケーションのマップとを記憶するメモリと、
プリコンディショナー行列を求める少なくとも１つのプロセッサであって、前記プリコンディショナー行列は、ブロック三角対角行列ではなく、該プロセッサは、前記ロケーションのマップにおいて有意であると識別された前記プリコンディショナー行列のロケーションにおいてのみ前記近似的な係数行列のエントリーを求め、該プロセッサは、前記プリコンディショナー行列の因数分解を有する反復方法を用いて前記正確な係数行列を有する行列方程式を解いて、前記正確な係数行列を有する連立方程式の解ベクトルを生成する、少なくとも１つのプロセッサと、
前記解ベクトルを用いて前記システムを制御する前記制御信号を生成するコントローラーと
を備える、モデル予測コントローラー。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、モデル予測制御に関し、より詳細には、動的システムの前処理付きモデル予測制御のための方法および装置に関する。
【背景技術】
【０００２】
モデル予測制御（ＭＰＣ）は、多くの用途において複合動的システムを制御するのに用いられる。そのようなシステムの例には、生産ライン、車両エンジン、ロボット、他の数値制御された機械加工、および発電機が含まれる。
【０００３】
ＭＰＣは、システムのモデルのリアルタイムな有限計画対象期間最適化に基づいている。ＭＰＣは、将来の事象を予期し、適切な制御動作を取る能力を有する。これは、制約を条件として将来の有限計画対象期間にわたってシステムの動作を最適化し、現在の時間ステップにわたる制御のみを実施することによって達成される。
【０００４】
ＭＰＣは、独立変数の変化によって引き起こされるモデル化されたシステムの従属変数の変化を予測することができる。化学プロセスでは、例えば、コントローラーが調整することができる独立変数は、多くの場合、圧力、流量、温度、弁の開度、およびダンパーの剛性である。コントローラーが調整することができない独立変数は、擾乱として扱われる。これらのプロセスにおける従属変数は、制御目標またはプロセス制約のいずれかを表す他の測定値である。
【０００５】
ＭＰＣは、システムのモデル、現在のシステム測定値、プロセスの現在の動的状態、並びにプロセス変数の目標および制限を用いて、従属変数の将来の変化を計算する。これらの変化は、独立変数および従属変数の双方に対する制約を条件として従属変数を目標の近くに保持するように計算される。
【０００６】
ＭＰＣ数値方法は、所与のシステム向けに特別に設計されることが多い様々な計算装置上で実施される。計算装置は、安価な固定小数点精度の組み込みコントローラーから高性能のマルチコアコンピュータープロセッサユニット（ＣＰＵ）、グラフィックス処理ユニット（ＧＰＵ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、または専用並列コンピュータークラスターにまで及ぶことができる。
【０００７】
モデル予測コントローラーは、プロセスの動的モデルに依拠し、最も多くは、線形経験モデルに依拠しており、この場合、ＭＰＣは、線形である。非線形モデルまたは非線形制約を用いてシステムを記述する非線形ＭＰＣ（ＮＭＰＣ）が、多くの場合、線形ＭＰＣと比較してより現実的であるが、計算がより難しくなる。線形ＭＰＣと同様に、ＮＭＰＣは、一般に凸ではない、有限予測計画対象期間に関する最適制御問題を解くことを要し、これは、数値解をリアルタイムで取得するための難題を提起する。ＮＭＰＣ最適制御問題の数値解は、多くの場合、ニュートン型最適化方式に基づいている。
【０００８】
正確なニュートン型最適化方式は、対応するヤコビ行列の解析表式を必要とし、この解析表式は、実際には稀にしか利用可能でなく、一般的には、前進差分（ＦＤ）近似に置き換えられる。そのような近似的なニュートン型最適化方式は、制御のあらゆる時間ステップの間、元の非線形方程式のＦＤ近似を利用する。
【０００９】
ＮＭＰＣへの適用において、そのような近似的なニュートン型最適化は、非特許文献１に記載されている継続ＮＭＰＣ（ＣＮＭＰＣ）数値方法によって実行することができる。ＣＮＭＰＣを用いたオンライン計算における重要で反復的な最も計算集約的ステップのうちの１つが行列方程式Ａｘ＝ｂの数値解法である。ここで、Ａは、係数行列であり、ｘは、解ベクトルであり、ｂは、ベクトルである。この解法は、制御の時間ステップごとに変化し、係数行列Ａおよびベクトルｂも同様である。
【００１０】
解ベクトルｘのエントリーは、ＭＰＣ方法の出力を決定し、この出力は、システムをリアルタイムで制御するシステムの入力制御パラメーターとして用いられる。したがって、例えば、安価な処理ユニットと、これらの処理ユニットに接続された、多くの場合に低速な限られた量のメモリとを用いた組み込み式ハードウェアコントローラー上の様々なＭＰＣの実施態様に現われる行列方程式Ａｘ＝ｂの高速かつ正確な解法を提供する方法が必要とされている。
【００１１】
ＣＮＭＰＣにおける係数行列Ａは、明示的には与えられず、行列ベクトル積を介してのみ利用可能である。具体的には、積Ａ＊Ｘを計算するのに、コンピューターコードが利用可能である。ここで、Ａは、係数行列であり、＊は、行列と行列との積であり、Ｘは、単一の列ベクトル、または行列に組み立てられるいくつかの列ベクトルである。この開示において、このコンピューターコードの動作は、「係数関数」の適用と呼ばれる。ベクトルに適用された係数関数は、係数行列とそのベクトルとの積を返す。内部的には、係数関数は、非特許文献１に記載されているように、例えば、複数の微分方程式を解くことによる状態方程式および共状態方程式の評価を必要とする。
【００１２】
係数行列Ａは、行列フォーマットではなく係数関数を介してのみ利用可能であるので、行列エントリーへのアクセスを必要とする直接的な行列ソルバーは、ＣＮＭＰＣでは用いられない。その代わり、係数行列Ａを有さず係数関数のみを有して動作することができるいわゆる「行列なし」反復方法が用いられる。ＣＮＭＰＣの行列方程式Ａｘ＝ｂを解くための１つの従来の行列なし反復方法は、一般化最小残差（ＧＭＲＥＳ）方法である。あらゆる時間ステップの間に非線形方程式のＦＤ近似にＧＭＲＥＳを用いることは、一般に、ＦＤＧＭＲＥＳと呼ばれ、不正確なニュートンの方法と解釈することができる。ＣＮＭＰＣに関して、ＦＤＧＭＲＥＳは、継続ＧＭＲＥＳ（Ｃ／ＧＭＲＥＳ）という名称が付けられている。
【００１３】
ＦＤＧＭＲＥＳには、係数関数を伴う行列ベクトル乗算が必要とされる。計算の全体的なコストは、ＦＤＧＭＲＥＳステップの最大数に比例する。ＦＤＧＭＲＥＳの収束が遅い結果、制御のオンライン計算が低速化し、コントローラーにおけるリアルタイム計算において取得される制御品質が低下する。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Ohtsuka, T.「A Continuation/GMRES Method for Fast Computation of Nonlinear Receding Horizon Control」（Automatica, Vol. 40, No. 4, pp. 563-574, Apr. 2004）
【発明の概要】
【発明が解決しようとする課題】
【００１５】
例えば、内点近似に基づくＣＮＭＰＣ方法および他の多くのＭＰＣ方法では、連立線形方程式のオンライン数値解法が、状態の数、制約、計画対象期間、および他の重要なＭＰＣ変数を制限する主要なボトルネックとなる可能性があり、このため、困難かつ高速な実用的システムに向けたＭＰＣの適用可能性が低減される。したがって、コントローラーにリアルタイムで必要とされる線形システムの反復解を得るためのプリコンディショナーを構築するシステムのモデル予測制御の効率性およびオンライン性能を高めることが望まれている。
【課題を解決するための手段】
【００１６】
モデル予測制御（ＭＰＣ）は、多くの用途において用いられる。継続ＭＰＣ（ＣＭＰＣ）等のいくつかのＭＰＣ方法は、変化する係数行列Ａおよび右辺のベクトルｂを有する行列方程式Ａｘ＝ｂを繰り返し解くことによって制御の解ベクトルｘを求める。制御の時間ステップごとに、ＭＰＣは、この解ベクトルｘから、システムを制御する制御動作を生成する。他の同様の例には、例えば、内点近似またはアクティブセット方法に基づくＭＰＣ方法が含まれる。
【００１７】
コントローラーの計算リソースに対して行列Ａのサイズが潜在的に大きいことおよび係数行列Ａの個々のエントリーが容易に利用可能でないことに起因して、行列方程式Ａｘ＝ｂの直接的な行列因数分解に基づくソルバーは、実用的でない。このため、行列方程式は、例えば、プリコンディショナー行列を有する反復方法を用いて反復的に解かれる。
【００１８】
前処理付き反復方法は、係数行列Ａを伴う行列ベクトル乗算を必要とし、全体的な計算コストは、最大反復数に比例する。係数行列Ａの計算の複雑さ、その変化する性質、および行列ベクトル乗算のみが必要であることに起因して、この反復方法は、係数行列をエントリー単位で用いる必要はなく、エントリー単位で明示的に求める必要さえもない。
【００１９】
その代わり、この反復方法は、ベクトルｙに適用されたときに係数行列Ａとベクトルｙとの積、すなわちａ（ｙ）＝Ａ＊ｙを返す係数関数ａ（  ）に依拠することができる。この係数関数は、オンラインの実施態様において制御の時間ステップごとにリアルタイムで生成されて用いられる。内部的には、係数関数の式の生成には、例えば、ＣＭＰＣにおいて、複数の微分方程式を解くことが必要とされる場合がある。
【００２０】
本発明の様々な実施の形態は、係数行列の計算の複雑さおよび係数関数の存在にもかかわらず、係数行列の必ずしも全てではなく一部のエントリーの近似的な値を明示的に求めることが有益である可能性があるという認識に基づいている。これは、前処理付き反復方法において係数行列を用いてプリコンディショナーを求め、反復数を削減することができるからである。ＭＰＣの計算の複雑さは、最大反復数に比例するので、いくつかの実施の形態によるプリコンディショナー行列は、ＭＰＣの複雑さを低減する。
【００２１】
本発明の様々な実施の形態は、前処理のために、係数行列のエントリーを求める必要はあるが、この求めることは、正確である必要はなく、近似的な係数行列を用いて近似することができるという別の認識に基づいている。いくつかのＭＰＣ方法、例えばＣＭＰＣでは、前処理のために、係数行列は、係数関数を用いて暗黙的に求められるが、この係数関数は、正確である必要はなく、近似的な係数関数によって近似することができる。近似的な形態であっても係数行列の各エントリーを求めることに係数関数を用いることによって、係数行列全体の枠組みは、保存され、プリコンディショナー行列を求めて適用するオンラインリアルタイム性能は改善される。
【００２２】
加えて、いくつかの実施の形態は、係数行列が既知であるかまたは正確な係数関数若しくは近似的な係数関数を用いて構成されるとき、行列内の特定のロケーション上のいくつかのエントリーが、他のロケーション上のエントリーよりも大きく、時にかなり大きいことがあるという認識に基づいている。その上、そのようなパターンは、制御システムの計算、インターラクションおよびタイプが異なっても繰り返すことができる。したがって、効率的なプリコンディショナー行列を構成するために、近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別するロケーションのマップをオフラインで求めることが可能である。
【００２３】
有意でない値は、ゼロおよび非ゼロの値を含むことができる。いくつかの実施の形態は、解ベクトルを求めるためには、非ゼロの有意でない値が重要であるという認識に基づいている。しかし、意外にも、複数の異なる試験および実験の後、プリコンディショナー行列を求めるために、それらの非ゼロの有意でない値の存在または不在は、前処理付き反復ソルバーの収束速度に対して最小限の影響しか与えないことが分かった。
【００２４】
したがって、本発明のいくつかの実施の形態は、ロケーションのマップにおいて有意であると識別されたロケーションにおいてのみ近似的な係数行列のエントリーを求めるかまたは更新し、マップによって求められたスパース性パターンを有するこの近似的な係数行列を用いてプリコンディショナー行列を求める。本発明のいくつかの実施の形態は、特に、有意なエントリーのロケーションの提案されたマップ用にオフラインで設計された行列並べ替えパターンもプリコンディショナー行列の列および行の順序付け並びに因数分解方法に用いて、その結果、ＭＰＣのオンラインのリアルタイムの実施態様における前処理を構成して適用する計算の複雑さが低下する。
【００２５】
したがって、本発明の１つの実施の形態は、システムのモデル予測制御（ＭＰＣ）の方法を開示する。本方法は、
ロケーションのマップにおいて有意であると識別されたロケーションにおいてのみ近似的な係数行列のエントリーをオンラインで求めることであって、前記エントリーは、前記ＭＰＣの正確な係数行列を近似するように求められ、前記ロケーションのマップは、前記近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別することと、
前記近似的な係数行列を用いて、プリコンディショナー行列の少なくとも一部分をオンラインで求めることであって、前記プリコンディショナー行列は、スパースであり、ブロック対角行列と異なるとともにブロック三角対角行列と異なることと、
前記プリコンディショナー行列を有する反復方法を用いて、前記正確な係数行列を有する前記ＭＰＣの行列方程式を解くことによって解ベクトルをオンラインで求めることと、
前記解ベクトルを用いて前記システムをリアルタイムで制御する制御信号をオンラインで生成することと、
を含む。本方法のステップは、少なくとも１つのプロセッサによって実行される
【００２６】
本発明の別の実施の形態は、各時間ステップにおいて生成された制御信号に従ってシステムを制御するモデル予測コントローラーであって、
前記システムのモデルと、近似的な係数行列および正確な係数行列と、前記近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別するロケーションのマップとを記憶するメモリと、
プリコンディショナー行列を求める少なくとも１つのプロセッサであって、前記プリコンディショナー行列は、ブロック（三角）対角行列ではなく、該プロセッサは、前記ロケーションのマップにおいて有意であると識別された前記プリコンディショナー行列のロケーションにおいてのみ前記近似的な係数行列のエントリーを求め、該プロセッサは、前記プリコンディショナー行列の因数分解を有する反復方法を用いて前記正確な係数行列を有する行列方程式を解いて、前記正確な係数行列を有する連立方程式の解ベクトルを生成する、少なくとも１つのプロセッサと、
前記解ベクトルを用いて前記システムを制御する前記制御信号を生成するコントローラーと、
を備える、モデル予測コントローラーを開示する。
【図面の簡単な説明】
【００２７】
【図１】本発明の実施の形態によるコントローラーおよびシステムのブロック図である。
【図２】本発明の実施の形態によるコントローラーのブロック図である。
【図３Ａ】本発明の実施の形態によるコントローラー上で実施されるモデル予測制御（ＭＰＣ）方法のブロック図である。
【図３Ｂ】本発明の１つの実施の形態によるシステムの継続ＭＰＣ（ＣＭＰＣ）の方法のブロック図である。
【図４Ａ】本発明のいくつかの実施の形態によるＭＰＣの行列方程式を解くプリコンディショナー行列を求めて用いる方法のブロック図である。
【図４Ｂ】本発明のいくつかの実施の形態によるＭＰＣの行列方程式を解くプリコンディショナー関数を求めて用いる方法のブロック図である。
【図４Ｃ】本発明のいくつかの実施の形態による行列方程式用の前処理付き反復ソルバーの一例を示す図である。
【図５】本発明のいくつかの実施の形態による非同期並行プリコンディショナーのセットアップのブロック図である。
【図６】本発明の１つの実施の形態に従って係数関数をベクトルに並行して適用することによって係数行列を求める本発明の１つの実施の形態の図である。
【図７】ベクトルのブロックに係数関数を適用する別の実施の形態の図である。
【図８】既に記憶されたベクトルのセットを完全な状態に完成させ、この完成したものに対して係数関数を評価する１つの実施の形態のブロック図である。
【図９】本発明の１つの実施の形態によるプリコンディショナーを求めるための上下（ＬＵ）三角分解／因数分解の図である。
【図１０】係数行列Ａの固有値分解を用いてプリコンディショナーを求める別の実施の形態の図である。
【図１１】固有値分解を用いてプリコンディショナー関数を変更する別の実施の形態の図である。
【図１２】本発明のいくつかの実施の形態によるシステムの継続モデル予測制御（ＣＭＰＣ）の方法のフローチャートである。
【図１３】行列ブロックの形態のＣＭＰＣの行列方程式の係数行列の概略図である。
【図１４】いくつかの無視できるほど小さなエントリーを有するＣＭＰＣの行列方程式の係数行列の行列ブロックと、これらの小さなエントリーの代わりにゼロエントリーを有する係数行列の対応する行列ブロックとの概略図である。
【図１５】本発明のいくつかの実施の形態による近似的な係数行列の要素を求める方法のフローチャートである。
【図１６Ａ】本発明の１つの実施の形態によるプリコンディショナーを求める係数行列の操作の概略図である。
【図１６Ｂ】本発明の１つの実施の形態によるプリコンディショナーを求める係数行列の操作の概略図である。
【図１６Ｃ】本発明の１つの実施の形態によるプリコンディショナーを求める係数行列の操作の概略図である。
【図１６Ｄ】本発明の１つの実施の形態によるプリコンディショナーを求める係数行列の操作の概略図である。
【図１６Ｅ】本発明の１つの実施の形態によるプリコンディショナーを求める係数行列の操作の概略図である。
【発明を実施するための形態】
【００２８】
本発明のいくつかの実施の形態は、モデル予測制御（ＭＰＣ）を用いた、システムの動作を制御するためのシステムおよび方法またはシステムのモデルに従ったシステムを提供する。
【００２９】
図１は、ＭＰＣコントローラー１１０に接続された一例示のシステム１２０を示している。コントローラー１１０は、このシステムのモデル１０２に従ってプログラムされる。このモデルは、システム１２０の状態１２１および出力１０３の経時的な変化を、現在および以前の入力１１１並びに以前の出力１０３の関数として表す一組の方程式とすることができる。このモデルは、システムの物理的限界および動作限界を表す制約１０４を含むことができる。動作中、コントローラーは、システムの所望の挙動を示すコマンド１０１を受信する。このコマンドは、例えば動きコマンドとすることができる。コマンド１０１の受信に応答して、コントローラーは、システムの入力としての役割を果たす制御信号１１１を生成する。この入力に応答して、システムは、システムの出力１０３および状態１２１を更新する。
【００３０】
本明細書において言及するようなシステムは、場合によっては、電圧、圧力、力等の物理量に関連付けられることがある或る特定の操作入力信号（入力）によって制御され、場合によっては、電流、流量、速度、位置等の物理量に関連付けられることがあるいくつかの制御された出力信号（出力）を返す任意の機械またはデバイスとすることができる。出力値は、一部分はシステムの以前の出力値に関係し、一部分は以前の入力値および現在の入力値に関係している。以前の入力と以前の出力との依存関係は、システムの状態に符号化される。システムの動作、例えば、システムのコンポーネントの動きは、或る特定の入力値の適用に続いてシステムによって生成される一連の出力値を含むことができる。
【００３１】
システムのモデルは、システム出力が現在の入力および以前の入力、並びに以前の出力の関数として経時的にどのように変化するのかを記述する一組の数学方程式を含むことができる。システムの状態は、システムのモデルおよび将来の入力とともに、システムの将来の動きを一意に規定することができる、一般に時変の任意の情報セット、例えば、現在のおよび以前の入力および出力の適切なサブセットである。
【００３２】
システムは、出力、入力、および場合によってはシステムの状態の操作が認められる範囲を制限する物理制約および仕様制約を受けることがある。
【００３３】
コントローラーは、固定または可変の制御周期サンプリング間隔で、システム出力およびシステムの動きの所望の動作を受信し、これらの情報を用いて、システムを動作させるための入力、例えば制御信号１１１を決定するハードウェア、またはプロセッサ、例えばマイクロプロセッサにおいて実行されるソフトウェアプログラムで実施することができる。
【００３４】
図２は、システムの状態１２１および出力１０３がコマンド１０１に従うようにシステムを作動させる本発明の実施の形態によるコントローラー１１０のブロック図を示している。コントローラー１１０は、モデル１０２およびシステムの動作に対する制約１０４を記憶するためのメモリ２０２に接続された単一のコンピュータープロセッサユニット（ＣＰＵ）または複数のＣＰＵ２０１を備える。コントローラーは、システム出力および状態がコマンド１０１に従うようにシステムを作動させる。
【００３５】
いくつかの実施の形態は、システムの計画対象期間にわたるモデル予測制御（ＭＰＣ）、具体的には、変化する係数行列Ａおよびベクトルｂを有する行列方程式Ａｘ＝ｂを繰り返し解くことによって制御における変化を含む解ベクトルｘを求めるタイプのＭＰＣのシステムおよび方法を提供する。各時間ステップにおいて、ＭＰＣは、解ベクトルｘからシステムを制御する制御動作を生成する。いくつかの実施の形態は、非線形モデルを用いてシステムを記述する非線形ＭＰＣ（ＮＭＰＣ）を用いる。それらの実施の形態では、ＣＭＰＣは、実際にはＣＮＭＰＣである。
【００３６】
図３Ａは、本発明のいくつかの実施の形態によるシステムのＭＰＣの方法のブロック図を示している。本方法は、コントローラー１１０のコンピュータープロセッサ２０１によっておよび／またはコントローラーのプロセッサと同時に動作する追加のプロセッサを用いて実行することができる。この例では、制御の現在の時間ステップにおけるコントローラーは、測定された状態１２１によってアクティブ化される。システムのモデル１０２および制約１０４は、コントローラーのメモリ２０２に記憶される。
【００３７】
図３Ａにおける方法は、現在の状態１０３の測定された値と、制御の以前の時間ステップの計画対象期間にわたって求められた状態および制御の値３１０とに基づいて、システムを制御する制御信号１１１を生成するオンライン制御ステップを実行する。本方法は、システムモデル１０２、制約１０４、コマンド１０１、現在の状態１０３、並びに利用可能である場合には、以前の時間ステップからの状態および制御を用いて、係数行列３４５を生成する（３４０）。本方法は、係数行列３４５を用いて、計画対象期間にわたる制御信号の変化を含むベクトルｘの行列方程式Ａｘ＝ｂを解き（３５０）、制御信号１１１の解ベクトル３５５を生成する。解く（３５０）ために、係数行列Ａ３４５が、モデルおよび制約、並びに現在の状態１０３を用いて求められる（３４０）。解ベクトルが求められた後、本方法は、制御信号１１１を生成し（３６０）、計画対象期間にわたる状態および制御の値を更新する。これらの更新された値は、その後、制御の次の時間ステップにおいて本方法によって用いられる。いくつかの実施の形態では、本方法は、計画対象期間にわたる時間間隔全体の制御を求める（３６０）が、ＭＰＣによって規定されるように最も近い時間ステップの制御信号１１１のみを出力する。
【００３８】
いくつかの実施の形態は、システムの継続モデル予測制御（ＣＭＰＣ）のシステムおよび方法を提供する。ＣＭＰＣは、変化する係数行列Ａおよびベクトルｂを有するＣＭＰＣの行列方程式Ａｘ＝ｂを繰り返し解くことによって制御の解ベクトルｘを求めるタイプのＭＰＣの特定の例である。各時間ステップにおいて、ＣＭＰＣは、解ベクトルｘから、システムを制御する制御動作を生成する。いくつかの実施の形態は、非線形モデルを用いてシステムを記述する非線形ＭＰＣ（ＮＭＰＣ）を用いる。それらの実施の形態では、ＣＭＰＣは、実際にはＣＮＭＰＣである。
【００３９】
図３Ｂは、本発明のいくつかの実施の形態によるシステムの継続モデル予測制御（ＣＭＰＣ）のための方法のブロック図を示している。本方法は、コントローラー１１０のコンピュータープロセッサ２０１によっておよび／またはコントローラーのプロセッサと並行して動作する追加のプロセッサを用いて実行することができる。この例では、制御の現在の時間ステップｔにおけるコントローラーは、測定された状態１２１によってアクティブ化される。システムのモデル１０２および制約１０４は、コントローラーのメモリ２０２に記憶される。
【００４０】
図３Ｂの方法は、現在の状態１０３の測定された値と、制御の以前の時間ステップの計画対象期間にわたって求められた状態、制御、ラグランジュ乗数の値３１０とに基づいてシステムを制御するための制御信号１１１を生成するオンライン制御ステップを実行する。
【００４１】
例えば、本方法は、値１０３および３１０を用いて微分方程式を解くことによってシステムのモデルに従って計画対象期間における予測された状態３２５を求め（３２０）、この予測された状態３２５から、カルーシュ−キューン−タッカー（ＫＫＴ）最適性必要条件に従って計画対象期間における予測された共状態３３５を求める（３３０）。
【００４２】
本方法は、モデル、ラグランジュ乗数、状態３２５および共状態３３５、並びに値３１０を用いて係数関数３４５１を生成する（３４０）。本方法は、係数関数３４５１を用いて、計画対象期間にわたる制御信号およびラグランジュ乗数の変化を含むベクトルｘの、係数行列Ａ３４５を有する行列方程式Ａｘ＝ｂを解いて（３５０）、制御信号１１１の解ベクトル３５５を生成する。解３５０について、係数行列Ａ３４５は、係数関数３４５１によって暗黙的に与えられる。解ベクトル３５５が求められた後、本方法は、制御信号１１１を生成し（３６０）、計画対象期間にわたる状態、制御、およびラグランジュ乗数の値を更新する（３６０）。更新された値は、制御の次の時間ステップにおいて本方法によって用いられる。
【００４３】
いくつかの実施の形態では、本方法は、計画対象期間にわたる全時間間隔の制御を決定する（３６０）が、ＭＰＣによって規定されるような最も近い時間ステップの制御信号１１１しか出力しない。
【００４４】
係数行列Ａの計算の複雑さ、その変化する性質、および行列ベクトル乗算が必要であることに起因して、ＭＰＣは、通常、係数行列Ａ３４５をエントリー単位で用いず、エントリー単位で明示的に求めることさえもない場合がある。その代わり、ＭＰＣは、係数関数３４５１に依拠する。ベクトルｙに適用された係数関数ａ（ｘ）３４５１は、係数行列Ａ３４５とベクトルｙとの積、すなわちａ（ｙ）＝Ａ＊ｙを返す。内部的には、係数関数３４５の式の生成３４０には、例えば、ＣＭＰＣにおいて、状態３２５について微分方程式を解き（３２０）、次いで、共状態３３５について微分方程式を解く（３３０）ことが必要とされる場合がある。
【００４５】
本発明の様々な実施の形態は、行列方程式Ａｘ＝ｂを解く。ここで、係数行列Ａ３４５は、係数関数３４５１によって定義される。コントローラーの計算リソースに対して行列サイズが潜在的に大きいこと、および係数行列Ａ３４５の個々のエントリーが容易に利用可能でない場合があることに起因して、行列方程式Ａｘ＝ｂの従来の直接的な行列因数分解に基づくソルバーは、実用的でないと考えられる。このため、ＭＰＣは、例えば、前処理付き一般化最小残差（ＧＭＲＥＳ）方法等の前処理付き反復方法を用いて、係数行列Ａ３４５を有する行列方程式Ａｘ＝ｂを反復的に解くことを伴う。したがって、本発明のいくつかの実施の形態は、プリコンディショナー行列を有する反復方法を用いて行列方程式を解く。
【００４６】
行列ＡのプリコンディショナーをＴとする。線形連立方程式Ａｘ＝ｂは、前処理付き定常反復方法ｘｎ＋１＝ｘｎ＋Ｔ（ｂ−Ａｘｎ）によって解くことができる。この定常反復は、ｘｎ＝ｘ０＋ｙｎの形態の解の最良の近似を探索する前処理付き最小残差方法、前処理付き一般化最小残差方法および前処理付き勾配方法等のクリロフ部分空間方法によって高速化することができる。ここで、ベクトルｙｎは、ベクトルＡｋ（ｂ−Ａｘ０）、k＝０，１，．．．，ｎ−１が張るクリロフ部分空間に属する。他の高速化反復には、特殊な多項式表現ｘｎ＝ｘ０＋ｐｎ（Ａ）（ｂ−Ａｘ０）によって解を近似するチェビシェフ方法およびネステロフ方法が含まれる。ここで、ｐｎ（Ａ）は、次数ｎのチェビシェフ多項式またはネステロフ多項式のいずれかである。
【００４７】
本発明のいくつかの実施の形態は、係数行列Ａ３４５の計算の複雑さおよび係数関数の存在にもかかわらず、係数行列Ａ３４５自体の少なくともいくつかのエントリーを明示的に求めることが有益である可能性があるという認識に基づいている。これは、係数行列Ａ３４５を用いて前処理付き反復方法においてプリコンディショナーを求めて、反復回数を削減することができるからである。ＣＭＰＣの計算コストは、最大反復回数に比例するので、係数関数に基づいて求められたプリコンディショナーの使用によって、ＣＭＰＣのコストを削減することができる。
【００４８】
本発明のいくつかの実施の形態は、前処理のために、係数関数を用いて係数行列の各エントリーを求めることができるが、係数関数は、正確である必要はなく、近似的な係数関数とすることができるという別の認識に基づいている。近似的な形式であっても、係数行列の各エントリーを求めるのに係数関数を用いることによって、係数行列全体にわたるＣＭＰＣの枠組みは、保存され、プリコンディショナーを求めるのに用いられる係数行列の品質は、是認される。加えてまたは代替的に、近似的な係数関数は、係数行列のエントリーを明示的に求めることがなくても、プリコンディショナーを求めるのに用いることができる。
【００４９】
図４Ａは、本発明の１つの実施の形態によるシステムのモデル予測制御（ＭＰＣ）の方法のブロック図を示している。この実施の形態は、正確な係数行列３４５および近似的な係数行列４９０のうちの一方またはそれらの組み合わせを用いて、プリコンディショナー４００の少なくとも一部分を求め（４０１）、次いで、プリコンディショナー行列を用いた制御の現在の時間ステップにおいて正確な係数行列３４５１を有するＣＭＰＣの行列方程式を解くことによって解ベクトル３５５を求める（４０２）。ここで、プリコンディショナー行列は、スパースであり、ブロック（三角）対角と異なる。この実施の形態は、解ベクトル３５５を用いてシステムを制御するための制御信号１１１を生成する（４０３）。
【００５０】
正確な係数行列４１０とは、本明細書において用いられるとき、制御の現在の時間ステップにおける制御の解ベクトル３５５を求める（３５０）のにコントローラーによって用いられる係数行列３４５である。それ以外のどの係数行列も近似的である。例えば、近似的な係数行列４９０は、制御の異なる時間ステップについて求められた異なる正確な係数関数４１０、または正確な係数行列を求めるための算術計算の精度よりも低い精度を有する算術計算を用いて求められた係数行列として求めることができる。近似的な係数行列４９０のエントリーは、正確な係数行列４１０のエントリーを近似したものである。
【００５１】
図４Ｂは、本発明の１つの実施の形態によるシステムの継続モデル予測制御（ＣＭＰＣ）の方法のブロック図を示し、正確な係数関数４１０１および近似的な係数関数４９０１は、正確な係数行列４１０および近似的な係数行列４９０を求める。この実施の形態は、正確な係数行列４１０および近似的な係数行列４９０のうちの一方またはそれらの組み合わせを用いてプリコンディショナー４００の少なくとも一部分を求め（４０１）、次いで、プリコンディショナー行列４００を有する反復方法を用いた制御の現在の時間ステップにおいて正確な係数関数４１０１によって定義された正確な係数行列４１０を有するＣＭＰＣの行列方程式を解くことによって、解ベクトル３５５を求める（４０２）。この実施の形態は、解ベクトル３５５を用いてシステムを制御するための制御信号１１１を生成する（４０３）。
【００５２】
正確な係数関数４１０１とは、本明細書において用いられるとき、制御の現在の時間ステップにおける制御の解ベクトルを求めるのにコントローラーによって用いられる係数関数である。それ以外のどの係数関数も近似的である。例えば、近似的な係数関数４９０１は、制御の異なる時間ステップについて求められた異なる正確な係数関数、または正確な係数関数を求めるための算術計算の精度よりも低い精度を有する算術計算を用いて求められた係数関数、または微分方程式の単純化されたソルバーを用いて求められた係数関数である。
【００５３】
特に、ベクトルに適用された近似的な係数関数４９０１は、そのベクトルへの正確な係数関数４１０１の適用の結果を近似する。具体的には、ベクトルに適用された近似的な係数関数４９０１は、近似的な係数行列４９０とそのベクトルとの積を返し、そのベクトルに適用された正確な係数関数４１０１は、制御の現在の時間ステップの正確な係数行列４１０とそのベクトルとの積を返す。
【００５４】
近似的な係数関数を用いてプリコンディショナー４００の少なくとも一部分を求めることは、係数行列３４５の個々のエントリーおよび／またはプリコンディショナー４００を求める際の柔軟性を提供し、空間、時間、および／または品質においてプリコンディショナーの種々の部分を求めることの分割を可能にする。これは、近似的な係数関数４９０１および正確な係数関数４１０１のうちの一方またはそれらの組み合わせの使用が、異なるプロセッサ上で、制御の異なる時間ステップにおいて、異なる正確さで、同じ係数行列３４５の異なるエントリーを求めることを可能にするとともに、プリコンディショナー４００を求めるためのＣＭＰＣの枠組みを依然として保存しているからである。
【００５５】
図４Ｃは、本発明の１つの実施の形態による正確な係数行列Ａ４１０として定義された係数行列３４５と、正確な係数関数４１０１とを用いてＭＰＣの行列方程式Ａｘ＝ｂを解くための前処理付き反復方法の一例を示している。この反復方法の一例は、前処理付き一般化最小残差（ＧＭＲＥＳ）方法である。
【００５６】
正確な係数関数４１０１は、制御の現在の時間ステップごとに求められる。代替的にまたは加えて、正確な係数行列４１０は、現在の時間ステップごとに求められる。また、解ベクトルｘの初期近似４９１が求められる。例えば、ゼロベクトルまたは制御の以前の時間ステップにおいて求められた解ベクトルは、いくつかの可能な選択肢である。
【００５７】
ＭＰＣの反復方法は、あらゆる反復において、正確な係数行列Ａを用いるかまたは正確な係数関数ａ（ｙ）を伴う行列ベクトル乗算４２０  Ａ＊ｙを必要とする。ここで、ベクトルｙは、解Ａｘ＝ｂの現在の近似ｘとすることができる。計算の全体的なコストは、最大反復回数に比例する。停止判定基準４３０は、現在の近似値ｘが所与の許容範囲を満たすか否か、または反復ステップの最大数ｋｍａｘに達したか否かを調べる。停止判定基準が満たされている場合（４３５）、反復は、停止し、ベクトルｘの現在の近似値が、行列方程式Ａｘ＝ｂの近似解４８０として出力される。停止判定基準が満たされていない場合（４３６）、解の更新された近似値４４０が計算され、反復は、ステップ４２０へのサイクルを続け、反復インデックスｋが１だけ増加される（４７０）。
【００５８】
いくつかの実施の形態は、近似的な係数行列４９０を用いて、プリコンディショナー行列４００の少なくとも一部分を求めるかまたは更新する（４５０）。プリコンディショナーは、最初に生成することができ、その後、例えば、メイン反復サイクルのあらゆるステップに対して適用することができる。いくつかの実施の形態では、プリコンディショナー行列は、メイン反復サイクルの外部で生成された（４５０）前処理関数ｔ（）に関係しており、ベクトルに適用されたこの前処理関数ｔ（ｘ）＝Ｔ＊ｘは、ベクトルｘに対するプリコンディショナー行列の逆行列Ｔの積Ｔ＊ｘを返す。
【００５９】
プリコンディショナーは、例えば、メイン反復サイクルのあらゆるステップの間に適用することができる（４６０）。プリコンディショナーの適用４６０は、例えば、プリコンディショナー関数ｔ（  ）が残差ｂ−Ａｘに作用する、すなわち、ｔ（ｂ−Ａｘ）を求めることを意味することができる。前処理の適用によって、反復あたりの計算コストを大幅に増加させることなく、反復方法の収束が加速され、したがって、コントローラーの全体的な性能改善がもたらされる。
【００６０】
近似的な係数行列Ａの近似的な逆行列が、プリコンディショナーの行列形式Ｔ４５０に用いられる場合、すなわち、Ｔ≒Ａ−１である場合、前処理付き反復方法における反復回数は、根本的に削減される。所与の時間ステップにおけるプリコンディショナーＴが、正確な係数行列４１０の逆行列と一致する正確な場合、すなわち、Ｔ＝Ａ−１である場合、前処理付き方法における反復回数は、１に削減される。しかしながら、この正確な場合は、計算的に高価である可能性があり、したがって、本発明のいくつかの実施の形態は、前処理更新またはセットアップ４５０および適用４６０を行う目的のために、近似的な係数行列（および／または近似的な係数関数）４９０が、それらの正確な対応するものと比較して、生成および適用がより容易で高速である可能性があるとともに、依然として高品質の前処理をもたらすことができるという認識に基づいている。
【００６１】
例えば、１つの実施の形態は、正確な係数関数を求めるための算術計算の精度よりも低い精度を有する算術計算を用いて近似的な係数関数を求める。この実施の形態は、プリコンディショナーＴを求める目的で係数行列Ａを作成および更新することは、完全な正確さを必要とせず、コンピューターベースのコントローラー上で削減された算術計算ビット数を用いて行うことができるという認識に基づいている。加えてまたは代替的に、別の実施の形態は、既に計算された近似的な係数行列関数または近似的な係数行列から低い精度の算術計算でプリコンディショナーＴを求めるものである。
【００６２】
例えば、２倍の算術計算精度を有する従来のコンピューター処理ユニット（ＣＰＵ）と、単一の算術計算精度を有するＧＰＵとを有する混合タイプの計算環境では、制御の計算は、倍精度のＣＰＵ上で実行することができる一方、プリコンディショナーの更新またはセットアップ４５０は、近似的な係数行列Ａの並列計算を含めて、単一精度のＧＰＵ上で実行することができる。
【００６３】
加えてまたは代替的に、別の実施の形態は、微分方程式用の単純化されたソルバーを用いて近似的な係数関数を求める。ここで、この単純化されたソルバーは、正確な係数関数を求めるためのソルバーよりも高速であるが、このソルバーよりも正確でない。例えば、ステップ３２０および３３０において微分方程式を解くためのソルバーは、近似的な係数関数を求めるためのソルバーの時間領域および／または空間領域において場合によっては、不均一な初期のグリッドと比較して、より大きなサイズを用いることができる。これは、オンライン計算の速度を増加させることができる一方、その結果削減された正確さは、プリコンディショナーの更新またはセットアップ４５０にのみ影響し、実際に計算される解４８０および制御信号１１１の正確さには影響しない。
【００６４】
加えてまたは代替的に、別の実施の形態は、システムの単純化された近似的なモデル１０２を用いて、プリコンディショナーの更新またはセットアップ４５０用の近似的な係数行列４９０または係数関数４９０１を求める。この実施の形態は、正確な係数関数を求めるのに用いられるシステムのモデルを近似し、このシステムの近似的なモデルを用いて近似的な係数関数を求める。そのようなモデルの近似および／または単純化の例には、ＮＭＰＣの線形化、元の計画対象期間よりも短い期間の使用、および制約の単純化のうちの１つまたはそれらの組み合わせが含まれるが、これらに限定されるものではない。
【００６５】
いくつかの実施の形態は、係数関数４１０１ａ（  ）、したがって、係数行列４１０Ａが、時間ステップごとに変化する可能性があるが、例えばＮＭＰＣにおける連続最適制御問題は、互いに類似している可能性があるので、この変化は、多くの場合、穏やかなものであるという別の認識に基づいている。
【００６６】
図５は、本発明のいくつかの実施の形態による、事前に求められたプリコンディショナーを更新するための方法のブロック図を示している。例えば、行列方程式を解く（５３０）のに用いられる係数関数は、正確な係数関数４１０１である。しかしながら、制御の次の時間ステップでは、この正確な係数関数は、近似的な係数関数４９０１となり、プリコンディショナーを更新する（５２０）のに用いることができる。いくつかの実施の形態では、更新５２０は、解く（５３０）こととは非同期に、例えば並列に行われる。例えば、解くことが、プロセッサ５１０によって実行される場合、更新５２０は、１つのまたは複数の異なるプロセッサ５１５によって実行される。他の実施の形態は、非同期的に、かつ、例えば追加のＣＰＵまたはＧＰＵ上でのＡｘ＝ｂの反復ソルバーの実行と同時（すなわち、並列）にプリコンディショナーを求めることができるかまたは更新することができるという認識に基づいている。
【００６７】
いくつかの実施の形態では、近似的な係数関数４９０１は、プリコンディショナーの一部分のみを更新する（５２０）。この更新は、制御の異なる時間ステップにおいて繰り返し実行される。このため、この実施の形態は、複数の近似的な係数関数および／または正確な係数関数、並びに複数のプリコンディショナーを用いてプリコンディショナーを求める。そのような更新は、プリコンディショナーを求めることを、異なる時点において求められた異なる係数関数を用いることによって時間において分割することと、追加のプロセッサを用いてプリコンディショナーの同じ部分または異なる部分を更新することによって空間において分割することとを可能にする。
【００６８】
いくつかの実施の形態は、近似的な係数関数および正確な係数関数のうちの一方またはそれらの組み合わせを用いて求められた係数行列に基づいてプリコンディショナーを求める。例えば、係数行列が、プリコンディショナーをセットアップする時間ステップごとに正確に求められる場合、前処理付き反復方法における反復回数を１に削減することができる。係数行列が、プリコンディショナーのセットアップのためにのみ近似的であるとき、反復回数は、１よりも多くなる可能性があるが、それでも、前処理のない従来の場合と比較して少なくすることができる。したがって、いくつかの実施の形態は、プリコンディショナーを求める目的で係数関数の正確なものの計算のコストと、前処理付き反復方法における反復回数の削減との間のトレードオフを提供する。
【００６９】
例えば、１つの実施の形態は、以前の時間ステップの正確な係数行列Ａから求められたプリコンディショナーをいくつかの後続の時間ステップに再利用する。これらの後続の時間ステップにおいて、正確な係数行列Ａは、変化する場合があり、そのため、プリコンディショナーは、現在の正確な係数行列Ａの近似値から求められる。この実施の形態は、プリコンディショナーの品質を監視し、その品質が低下したとき、プリコンディショナーを再計算することができる。例えば、この実施の形態は、前処理付き反復方法の収束速度が閾値未満であるとき、プリコンディショナーを再計算することができる。
【００７０】
代替的に、１つの実施の形態は、現在の時間よりも前のいくつかの時間ステップにおいて、予測された将来の状態について計算された係数行列から求められたプリコンディショナーをいくつかの後続の時間ステップに再利用する。この実施の形態は、ＭＰＣプロセスが、制御および予測される将来の状態を計画対象期間内に計算するという認識に基づいている。ＭＰＣは、次の時間ステップの制御のみをシステムに出力し、他の全ての計算された量を破棄するが、それらの量は、プリコンディショナーを求めるのに用いることができる。別の実施の形態では、プリコンディショナーは、制御の異なる時間ステップからプリコンディショナーを用いて、例えば外挿を用いて求められる。
【００７１】
いくつかの実施の形態は、反復方法を停止して、プリコンディショナーを更新する。例えば、反復方法は、或る反復ステップにおいて停止することができ、その後、新しく再計算または更新されたプリコンディショナーとともに、解の現在の反復近似値を再開される方法の初期近似値として用いて再開することができる。この場合、再開と再開との間の反復のプロセス中、プリコンディショナーは、固定される。
【００７２】
代替的な実施の形態は、再開することなく、再計算または更新されたプリコンディショナーを反復ソルバーにおいて用い、これによって、可変のプリコンディショナー、すなわち、あらゆる反復において変化することができるプリコンディショナーが得られる。したがって、実施の形態は、柔軟な一般化最小残差（ＰＧＭＲＥＳ）方法、前処理付き最小残差（ＰＭＩＮＲＥＳ）方法、または前処理付き共役勾配（ＰＣＧ）方法等の可変の前処理を可能にする柔軟な反復方法を用いるように変更される。
【００７３】
加えてまたは代替的に、１つの実施の形態は、通常、所与の時間ステップにおいて開始する反復方法は、以前の時間ステップからの、おそらくは解の初期近似値から離れている情報を用いないという認識に基づいている。この情報は、収束を加速するのに利用価値がある場合があるので、この実施の形態は、時間ステップ間で反復方法を再開するのではなく、更新された係数行列Ａ（更新された係数関数によって与えられる）および更新されたベクトルｂを用いて反復の実行を維持する。この実施の形態は、可変の前処理に対してだけでなく、更新された係数行列Ａおよびベクトルｂに対しても柔軟な反復方法を用いる。
【００７４】
本発明のいくつかの実施の形態は、コントローラーメモリに記憶された正確な係数行列Ａのエントリーのうちの少なくともいくつかを近似するプリコンディショナーを求める。係数行列Ａのエントリーが例えばＣＭＰＣにおいて当初明示的に利用可能でないときの適用では、いくつかの実施の形態は、近似的な係数行列または正確な係数行列の各エントリーを求める。例えば、１つの実施の形態は、近似的な係数関数および正確な係数関数のうちの一方またはそれらの組み合わせを用いて近似的な係数行列の各エントリーを求め、この近似的な係数行列を用いてプリコンディショナーを求める。
【００７５】
１つの実施の形態は、ロケーションのマップにおいて有意であると識別されたロケーションにおいてのみ近似的な係数行列のオンラインエントリーを求め、このロケーションのマップは、近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別する。
【００７６】
さらに、別の実施の形態は、有意なロケーションのマップをオフラインで求め、有意でないとしてマッピングされたロケーションは、プリコンディショナー行列内のロケーションにおける近似的な係数行列のエントリーを無効にすることがプリコンディショナー行列を有する反復方法の収束速度を所定の第１の閾値よりも大きく維持するか否かを調べることによる解析的導出および数値シミュレーションのうちの一方またはそれらの組み合わせによって求められる。プリコンディショナー行列内のロケーションにおける近似的な係数行列のエントリーを無効にすることが反復方法の収束速度を維持するか否かを調べる解析的導出および数値シミュレーションには、オンライン制御のための正確な係数行列４１０全体をオフラインで求めることが必要となる場合がある。
【００７７】
代替的にまたは加えて、異なる実施の形態は、有意なロケーションのマップをオフラインで求める。これらの有意なロケーションは、近似的な係数行列の絶対値エントリーによる最大のもののロケーションとして求められ、ロケーションのマップによって有意であると識別された非ゼロのエントリーの数は、近似的な係数行列のエントリーの総数の所定の割合および近似的な係数行列の有意なエントリーの絶対値未満の境界を定める所定の第２の閾値のうちの一方またはそれらの組み合わせによって求められる。近似的な係数行列の絶対値エントリーによる最大のもののロケーションを求めることは、オンライン制御のための正確な係数行列４１０全体をオフラインで求めることによって数値的に行うことができる。
【００７８】
図６は、係数関数ａ（  ）６０１を座標ベクトルｅｉ、すなわち係数行列Ａのサイズの単位行列Ｉの列または任意のフルランク行列Ｚの列ｚｉに適用することによって係数行列を求める（６００）、本発明の１つの実施の形態のフローチャートを示している。係数関数６０１は、正確な係数関数または近似的な係数関数である。
【００７９】
例えば、いくつかの実施の形態は、係数関数６０１をベクトルｚｉのそれぞれに並行して（６１０）適用して（６２０）、行列ＡＺ６３０を取得する。これらの実施の形態は、行列ＡＺに行列Ｚの逆行列を右側から乗算することによって、係数行列Ａを正確または近似的に求める（６４０）。いくつかの変形形態では、行列Ｚは、単位行列Ｚ＝Ｉである。それらの変形形態では、乗算６４０は必要ではない。
【００８０】
係数行列Ａが適切に定式化された場合、この係数行列は、対称形である。したがって、いくつかの実施の形態は、この係数行列Ａの上三角部分または下三角部分のみを求める。それにもかかわらず、実施の形態のうちのいくつかでは、便宜上または速度のために、完全な係数行列Ａが計算される。
【００８１】
コントローラーのいくつかの実施態様では、計算された完全な係数行列Ａは、正確には対称形でない場合があり、これは、前処理および反復方法において数値の誤りをもたらす可能性がある。したがって、１つの実施の形態は、係数行列をその対称平均（Ａ＋ＡＴ）／２に置き換える（６５０）ことによって係数行列を正確に対称形にする。ループ６１０内の計算６２０は、互いに完全に独立しているので、この実施の形態は、複数のプロセッサ、例えばＧＰＵまたはＦＰＧＡを用いたマルチスレッド（並列）計算を利用することができる。したがって、この実施の形態は、係数行列の要素を並列に求めることができ、これによって、計算効率が高められる。
【００８２】
図７は、同じプロセッサ上で、単一のベクトルａ（ｚ）ではなくベクトルのブロックＺに係数関数ａ（Ｚｊ）を適用することによって係数行列を求める（７００）本発明の１つの実施の形態のフローチャートを示している。係数関数６０１から係数行列Ａを生成するためにここで用いられる行列Ｚは、その列ＺＪのブロックに事前に分割されている（７０１）必要がある。あらゆるブロックが、単一の列しか含まない場合、図７の実施の形態は、図６の実施の形態と同様である。そうでない場合、ステップ７１０、７２０、および７３０は、ステップ６１０、６２０、および６３０を一般化したものである。いくつかの変形形態では、行列Ｚは、単位行列Ｚ＝Ｉである。それらの変形形態では、乗算６４０は、必要ではない。
【００８３】
同じプロセッサ上で係数関数をベクトルのブロックに適用することによって、１つの実施の形態は、高レベル基本線形代数サブプログラム（ＢＬＡＳ）、またはそれらの類似の代替のものを利用することが可能になる。ＢＬＡＳは、ベクトルおよび行列を用いた共通の線形代数演算を実行する低レベルカーネルサブルーチンのセットである。高レベルＢＬＡＳ、すなわち、ＢＬＡＳレベル２およびＢＬＡＳレベル３は、特に、データおよび命令のパイプライン化、いくつかの機能ユニットを用いた内部マルチスレッド化、およびマルチレベル内部キャッシュメモリを有するベクトルプロセッサ上でＢＬＡＳを用いてプログラムの性能を改善するように意図されている。いくつかの実施の形態では、所与のコントローラーコンピューターハードウェアが、一方では、複数のプロセッサを用いたマルチスレッド計算の機会と、他方では、ベクトルプロセッサが複数のデータおよび命令を取り扱う能力とをバランスさせるように、行列Ｚのブロックへの分割を最適化することができる。
【００８４】
いくつかの実施の形態は、近似的な係数行列の選択されたエントリーの所定のオフラインマップを用いてプリコンディショナー行列のエントリーをオンラインで求める。近似的な係数行列の選択されたエントリーは、以下のように近似的な係数関数を用いてオンラインで効率的に求めることができる。
【００８５】
図６のように、係数関数ａ（  ）６０１を座標ベクトルｅｉに適用することによって、係数行列の第ｉ列全体を求めることができる。図７のように、係数関数ａ（  ）６０１を座標ベクトルの関係するブロックに適用することによって、係数行列の列のブロック全体を求めることができる。係数行列の対応する行は、係数行列の対称性を用いて、転置演算を既に求められている列に用いることによって求めることができる。
【００８６】
係数行列の個々のエントリーは、例えば、システムモデル１０２および制約１０４を用いてオフラインで導出された解析公式を適用することによってオンラインで求めることができる。例えば、係数関数６０１が前進差分を解析的に導出された１次導関数に適用して取得されるＣＭＰＣでは、係数行列の個々のエントリーを記述する解析公式の個々のエントリーは、２次導関数を得ることによって取得することができる。
【００８７】
係数行列Ａのエントリーを入手することができることによって、行列係数関数ａ（  ）の逆関数を近似する前処理関数ｔ（  ）を求めることが可能になる。図８、図９および図１０は、プリコンディショナー行列の様々な行列因数分解および固有値分解または特異値分解に基づくプリコンディショナーの作成および更新を具体的に説明する例示の実施の形態の図を示している。
【００８８】
図８は、プリコンディショナー行列８００の上下（ＬＵ）三角因数分解（または分解）の一例を示している。近似的な係数行列Ａ８００は、事前に求められ、メモリに記憶される。プリコンディショナーセットアップ８１０が、三角因数分解Ａ＝ＬＵを求める。ここで、行列Ｌは、下三角行列であり、行列Ｕは、上三角行列である。プリコンディショナー関数ｔ（ｂ）の適用８２０は、次のステップを含む。行列方程式Ｌｙ＝ｂが、行列Ｌが下三角行列であることを用いて、後退代入によって解かれる（８３０）。行列方程式Ｕｚ＝ｙが、行列Ｕが上三角行列であることを用いて、後退代入によって解かれる（８４０）。最後に、プリコンディショナーが、ｔ（ｂ）＝ｚとして求められる（８５０）。
【００８９】
近似的な係数行列Ａが対称行列であるとき、下対角転置下側因数分解Ａ＝ＬＤＬＴが、ＬＵ因数分解よりも効率的である。Ａが対称正定値行列である場合、本発明の１つの実施の形態では、コレスキー因数分解Ａ＝ＬＬＴが前処理に用いられる。
【００９０】
いくつかの状況では、直交上側因数分解Ａ＝ＱＲまたはシュ−ル因数分解Ａ＝ＱＲＱＴが前処理に役立つ場合がある。ここで、Ｑは、直交行列であり、Ｒは、三角行列である。
【００９１】
図９は、直交変換Ｑを用いるとともに、対称反三角行列Ｋを選択することによって行列Ａの対称性を利用する反三角因数分解（または分解）Ａ＝ＱＫＱＴの図を示している。ここで、Ｔは、転置行列演算である。近似的な係数行列Ａ９００は、事前に求められ、メモリに記憶されている。プリコンディショナーのセットアップ９１０は、反三角因数分解Ａ＝ＱＫＱＴを求める。ここで、行列Ｑは、直交性を有し、行列Ｋは、対称反三角形である。プリコンディショナー関数の適用ｔ（ｂ）９２０は、次のステップを含む。行列Ｑの逆行列は、行列方程式の右辺ｂにｙ＝ＱＴｂとして適用される（９３０）。行列方程式Ｋｚ＝ｙは、行列Ｋが反三角形であることを用いて後退代入によって解かれる（９４０）。最後に、プリコンディショナーは、ｔ（ｂ）＝Ｑｚとして求められる（９５０）。
【００９２】
この反三角形分解に基づく前処理の結果、行列Ａが正定値でない場合には、正定値でない対称プリコンディショナーＴ＝Ａ−１が得られる。これは、適切な反復ソルバー、例えば前処理付きＧＭＲＥＳを選択する際に考慮に入れられる。
【００９３】
図１０は、図９の実施の形態に加えてまたはこれに代えて用いることができる別の実施の形態のブロック図を示している。この実施の形態では、プリコンディショナーのセットアップ１０１０は、行列Ａ＝ＶΣＶＴの固有値分解を求める。ここで、Ｖは、列固有ベクトルの直交行列であり、Σは、固有値から作成された対角行列であり、演算Ｔは、行列転置を表す。固有値分解は、ステップ１０３０、１０４０、および１０５０に示すように、Ｔ＝Ｖ｜Σ｜−１ＶＴによって与えられる対称正定値絶対値プリコンディショナー（ＡＶＰ）を作成するのに用いられる（１０２０）。直接的なソルバー１０４０では、この実施の形態は、対角行列Σの対角エントリーの絶対値を反転する。Ａが対称行列でないとき、ＡＶＰプリコンディショナーは、Ａの極分解またはＡの特異値分解によって構成される。
【００９４】
対称正定値ＡＶＰ  Ｔの利点は、前処理付きＭＩＮＲＥＳ反復方法の使用が、行列方程式Ａｘ＝ｂを解くことを可能にするということである。ＭＩＮＲＥＳは、前処理付きＧＭＲＥＳと比較して、より確実かつより高速に収束することでき、したがって、高速に変化するシステムを制御することが可能な高クロックレートを有する信頼できるコントローラーをもたらす。
【００９５】
図１１は、行列Ａの固有値分解または特異値分解を用いることによって前処理関数ｔ（  ）を変更する（１１２０）別の実施の形態を示している。この実施の形態は、プリコンディショナーがいくつかの時間ステップについて更新されていない場合、その品質が低下し、その結果、Ａｘ＝ｂを解くための前処理付き反復方法の収束が遅くなるという認識に基づいている。数学的には、そのような低速化は、行列Ａの条件数の増加に関係しており、プリコンディショナーを変更して、遅い収束の原因である行列Ａのいくつかの（閾値を用いる）特異ベクトルまたは固有ベクトルＹ１１００をデフレートまたは強化することによって取り除くことができる。
【００９６】
例えば、プリコンディショナーをＡＶＰ等の対称正定値とし、Ｙを、ｔ（Ａ）の絶対値固有値によるいくつかの最小値およびいくつかの最大値に対応する固有ベクトルである列を有する行列１１００を表すものとする。これらの固有ベクトルは、例えば、以前の時間ステップにおいて計算することができる。１つの実施の形態は、Ｙに含まれる固有ベクトルを検討から除外し、したがって、前処理付き反復ソルバーの収束を加速するデフレーションを用いて、前処理関数ｔ（  ）を新たな前処理関数ｔＹ（  ）に変更する（１１２０）。例えば、この実施の形態は、ｔＹ（  ）をｔＹ（）＝ＰＹｔ（）として数学的に定義する（１１３０）ことができる。ここで、ＰＹは、補空間における行列Ｙの範囲へのプロジェクター１１１０である。
【００９７】
加えてまたは代替的に、いくつかの実施の形態は、行列方程式Ａｘ＝ｂの反復ソルバーの遅い収束が、小次元部分空間に由来する場合があるという認識に基づいている。プリコンディショナー関数においてこの部分空間を検出し、これをデフレートすることによって、反復ソルバーの収束を加速させることができる。この部分空間は、誤差伝播演算子の固有ベクトルに関係し、以前の時間ステップにおいてまたは反復の過程において計算することができる。正確な係数関数は、あらゆる時間ステップにおいて変化するので、１つの実施の形態は、ＣＭＰＣ行列方程式Ａｘ＝ｂを解くための反復ソルバーの実行中およびこの実行と並行して、すなわち並列に、デフレートした部分空間の少なくとも一部分を更新する。
【００９８】
係数行列のスパース再構成
本発明のいくつかの実施の形態は、係数行列が正確な係数関数または近似的な係数関数を用いて構成されるとき、行列内の特定のロケーション上のいくつかのエントリーは、他のロケーション上のエントリーよりも大きく、時にかなり大きいこともあるという認識に基づいている。そのようなパターンは、制御システムの計算、インターラクションおよびタイプが異なっても繰り返すことができる。したがって、近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別するロケーションのマップをオフラインで求めることが可能である。
【００９９】
本発明のいくつかの実施の形態は、解ベクトルを求めるためには、非ゼロの有意でない値が重要であるという認識に基づいている。しかし、意外にも、複数の異なる試験および実験の後、プリコンディショナーを求めるために、それらの非ゼロの有意でない値の存在または不在は、反復ソルバーの収束に対して最小限の影響しか与えないことが分かった。
【０１００】
したがって、本発明のいくつかの実施の形態は、ロケーションのマップにおいて有意であると識別されたロケーションにおいてのみ近似的な係数行列のエントリーを更新し、この近似的な係数行列を用いてプリコンディショナーを求める。
【０１０１】
図１２は、上述した認識を利用した本発明の１つの実施の形態によるシステムの継続モデル予測制御の方法のブロック図を示している。この実施の形態は、ロケーションのマップ１２０５において有意であると識別されたロケーションにおいてのみ近似的な係数行列のエントリーを更新する（１２１０）。例えば、エントリーは、近似的な係数関数および正確な係数関数のうちの一方またはそれらの組み合わせを用いて、近似的な係数行列内のエントリーの各ロケーションを有意であるかまたは有意でないと識別するロケーションのマップに従って更新される。ロケーションのマップは、オフラインで求めて、プロセッサに作動接続されたメモリ、例えばメモリ２０２に記憶することができる。
【０１０２】
本方法は、近似的な係数行列を用いてプリコンディショナーを求め（１２２０）、このプリコンディショナーを有する反復方法を用いた制御の現在の時間ステップにおいて、正確な係数関数によって定義された係数行列を有するＣＭＰＣの行列方程式を解くことによって解ベクトルを求める（１２３０）。上記で説明したように、ベクトルに適用される近似的な係数関数は、正確な係数関数をベクトルに適用した結果を近似する。次に、本方法は、解ベクトルを用いてシステムを制御する制御信号を生成する。
【０１０３】
図１３は、ブロック形態１３００の係数行列の各ブロックエントリーを有意であるかまたは有意でないと識別するロケーションのマップの一例を示している。この例では、例えば、ロケーションのマップは、インデックス２２、２３、および３２を有するブロックを有意であると識別する一方、他の全てのブロックは、有意でない。この例におけるロケーションのマップは、有意でないブロックのロケーションを示す０のエントリーと、有意なブロックのロケーションのエントリー１とを有する３×３バイナリー行列１３１０とすることができる。対称係数行列の場合、有意性のインジケーター（０または１）のバイナリー行列も対称行列であり、このため、インジケーターのバイナリー行列の上三角部分のみを記憶する必要がある。ロケーションのマップは、異なる形態を有することができ、係数行列の各エントリーを個別に識別することもできるし、エントリーのグループまたはブロックの一部として、例えば行列ブロックの形態で識別することもできる。いくつかの実施の形態では、ロケーションのマップは、行列Ａをオンラインで実際に構成することなく、解析的または数値的にオフラインで求められる。
【０１０４】
例えば、いくつかの実施の形態では、係数行列は、ラグランジュ関数のヘッセ行列またはヘッセ行列のシュ−ル補行列である。ヘッセ行列は、スパースである。すなわち、そのエントリーのほとんどは０である。非ゼロのエントリーが、ロケーションのマップを規定し、いくつかのブロック対角若しくはブロック行およびブロック列、または双方の組み合わせを形成する。ブロックサイズは、通常、小さく、これによって、ロケーションのマップを解析的に求めることが可能になる。例えば、非ゼロのエントリーは、解析公式および／または係数関数によって定義することができる。
【０１０５】
同様に、ヘッセ行列のシュ−ル補行列は、非ゼロのエントリーのより複雑な構造を有し、この構造において、いくつかの非ゼロのエントリーは、有意でない。例えば、いくつかの変数の変動が、隣接した継続ステップ間でラグランジュ関数の閾値未満の変化を引き起こす場合、そのような変動は、破棄することができ、その結果、効率的な前処理に適した有意なエントリーの単純なスパース構造が得られる。この挙動は、状態変数および共状態変数について観測されることが多い。なぜならば、それらの変数は、ラグランジュ関数において時間ステップを乗算されるからである。
【０１０６】
図１４は、ロケーションのマップに従って求められたいくつかの無視できるほど小さなエントリー１４１０、１４２０、１４３０および１４４０を有するＣＭＰＣの行列方程式の係数行列Ａの行列ブロックと、それらの小さなエントリーの代わりにデフォルト値、例えば、ゼロエントリー１４１５、１４２５、１４３５、および１４４５を有する近似的な係数行列Ｍの対応する行列ブロックとを示している。そのようにして、ロケーションのマップは、近似的な係数行列Ｂのスパース性パターンを要素ごとまたはブロックごとに定義する。
【０１０７】
図１５は、正確な係数行列Ａを最初にオンラインで求めることなく、近似的な係数行列Ｂの行列ブロックを直接求める１つの実施の形態による方法のフローチャートを示している。この実施の形態は、ブロックスパース形態の近似的な係数関数を求め（１５１０）、近似的な係数行列Ｂの有意なエントリーのみを更新して（１５２０）、プリコンディショナー１５１５を求める。図１５の方法の結果、計算的に安価な高品質のプリコンディショナー１５１５が得られ、継続モデル予測制御に基づくコントローラーのより高速でより効率的なオンライン性能がもたらされる。
【０１０８】
１つの実施の形態では、前処理セットアップは、図８のように、近似的な係数行列Ｍ＝Ａの上下（ＬＵ）因数分解を含む。因数分解コストは、Ｍの非ゼロのエントリーの構造に依存する。非ゼロのエントリーが、例えば、矢印表示構造のような少数のブロック対角および／またはブロック行およびブロック列を含む場合、コストは少ない。その上、プリコンディショナーの適用のコストは、因数ＬおよびＵ内の非ゼロの要素の数に比例する。
【０１０９】
図１６Ａは、本発明の１つの実施の形態による継続モデル予測制御の最小時間問題について求められた係数行列Ａ１６１０の概略図を示している。係数行列Ａ１６１０は、スパースであるが、複数の非ゼロのエントリー１６２０を含む。これらのエントリー１６２０は、単一の要素または要素のブロックとすることができる。係数行列Ａの列は、係数関数ａ（  ）によって求められる。Ａのいくつかの非ゼロのエントリーは、小さな値、すなわち前処理にとって有意でない値であり、０に置き換えることができる。いくつかの実施の形態では、非有意性についての判定は、計算を伴うことなく解析的に行われる。
【０１１０】
図１６Ｂは、本発明の１つの実施の形態による係数行列１６１０の有意でないエントリーを０に置き換えた結果得られる近似的な係数行列Ｍ１６３０の概略図を示している。結果として得られた近似的な係数行列Ｍは、有利なスパース構造を有し、前処理行列として用いることができる。行列Ｍのエントリーのほとんどは、前処理のために近似的に求められる。いくつかの実施の形態は、状態変数および共状態変数の「フローズン」タイプの削除に基づいてエントリーを求める高速な公式を用いる。その結果、行列Ｍの全ての非ゼロのエントリーは、Ｏ（Ｎ）の算術演算によって計算することができる。ここで、Ｎは、後退ホライズン上のグリッド点の数である。
【０１１１】
図１６Ｃは、本発明の１つの実施の形態によって求められる並べ替えられた前処理行列
【数１】
2017084343.tif 000003
１６４０の概略図を示している。この実施の形態は、並べ替えられた前処理行列
【数２】
2017084343.tif 000004
１６４０の非ゼロの値を対角位置に向けて移動させるように行列Ｍ１６３０の列および行を並べ替える。例えば、この実施の形態は、並べ替えられた前処理行列
【数３】
2017084343.tif 000005
１６４０の対角が狭い帯を有する行列１６４５に収集されるように、行列Ｍの行および列の同時並べ替えＰを実行する。ＰＴＰ＝Ｉであるので、方程式Ｍｘ＝ｒは、方程式
【数４】
2017084343.tif 000006
と等価である。ここで、
【数５】
2017084343.tif 000007
である。そのような並べ替えによって、近似的な係数行列ＭのＬＵ因数分解は、単純化される。
【０１１２】
図１６Ｄおよび図１６Ｅは、本発明の１つの実施の形態による近似的な係数行列ＭのＬＵ因数分解の下三角因数Ｌの行列１６５０および上三角因数Ｕの行列１６６０の概略図を示している。この実施の形態では、行列
【数６】
2017084343.tif 000008
のＬＵ因数分解は、三角因数ＬおよびＵを有する。
【数７】
2017084343.tif 000009
であるので、前処理方程式Ｍｘ＝ｒの解は、単純化することができ、以下の式に従ってＯ（Ｎ）の算術演算でその値を求めることができる。
【数８】
2017084343.tif 000010
【０１１３】
本発明の上記の実施の形態は、数多くの方法のいずれかにおいて実現することができる。例えば、それらの実施の形態は、ハードウェア、ソフトウェアまたはその組合せを用いて実現することができる。ソフトウェアにおいて実現されるとき、そのソフトウェアコードは、単一のコンピューター内に設けられるにしても、複数のコンピューター間に分散されるにしても、任意の適切なプロセッサ、またはプロセッサの集合体において実行することができる。そのようなプロセッサは、集積回路として実現することができ、集積回路コンポーネント内に１つまたは複数のプロセッサが含まれる。しかしながら、プロセッサは、任意の適切な構成の回路を用いて実現することができる。
【０１１４】
また、本明細書において概説される種々の方法またはプロセスは、種々のオペレーティングシステムまたはプラットフォームのいずれか１つを利用する１つまたは複数のプロセッサ上で実行可能であるソフトウェアとしてコード化することができる。さらに、そのようなソフトウェアは、いくつかの適切なプログラミング言語および／またはプログラミングツール若しくはスクリプト記述ツールのいずれかを用いて書くことができ、フレームワークまたは仮想機械上で実行される実行可能機械語コードまたは中間コードとしてコンパイルすることもできる。通常、プログラムモジュールの機能は、種々の実施の形態において望ましいように、組合せることもできるし、分散させることもできる。
【０１１５】
また、本発明の実施の形態は、方法として具現することができ、その一例が提供されてきた。その方法の一部として実行される動作は、任意の適切な方法において順序化することができる。したがって、例示的な実施の形態において順次の動作として示される場合であっても、例示されるのとは異なる順序において動作が実行される実施の形態を構成することもでき、異なる順序は、いくつかの動作を同時に実行することを含むことができる。
【図１】
2017084343.tif 000011
【図２】
2017084343.tif 000012
【図３Ａ】
2017084343.tif 000013
【図３Ｂ】
2017084343.tif 000014
【図４Ａ】
2017084343.tif 000015
【図４Ｂ】
2017084343.tif 000016
【図４Ｃ】
2017084343.tif 000017
【図５】
2017084343.tif 000018
【図６】
2017084343.tif 000019
【図７】
2017084343.tif 000020
【図８】
2017084343.tif 000021
【図９】
2017084343.tif 000022
【図１０】
2017084343.tif 000023
【図１１】
2017084343.tif 000024
【図１２】
2017084343.tif 000025
【図１３】
2017084343.tif 000026
【図１４】
2017084343.tif 000027
【図１５】
2017084343.tif 000028
【図１６Ａ】
2017084343.tif 000029
【図１６Ｂ】
2017084343.tif 000030
【図１６Ｃ】
2017084343.tif 000031
【図１６Ｄ】
2017084343.tif 000032
【図１６Ｅ】
2017084343.tif 000033
【外国語明細書】
2017084343.tif 000034
2017084343.tif 000035
2017084343.tif 000036
2017084343.tif 000037
2017084343.tif 000038
2017084343.tif 000039
2017084343.tif 000040
2017084343.tif 000041
2017084343.tif 000042
2017084343.tif 000043
2017084343.tif 000044
2017084343.tif 000045
2017084343.tif 000046
2017084343.tif 000047
2017084343.tif 000048
2017084343.tif 000049
2017084343.tif 000050
2017084343.tif 000051
2017084343.tif 000052
2017084343.tif 000053
2017084343.tif 000054
2017084343.tif 000055
2017084343.tif 000056
2017084343.tif 000057
2017084343.tif 000058
2017084343.tif 000059
2017084343.tif 000060
2017084343.tif 000061
2017084343.tif 000062
2017084343.tif 000063
2017084343.tif 000064
2017084343.tif 000065
2017084343.tif 000066
2017084343.tif 000067
2017084343.tif 000068
2017084343.tif 000069
2017084343.tif 000070
2017084343.tif 000071
2017084343.tif 000072
2017084343.tif 000073
2017084343.tif 000074
2017084343.tif 000075
2017084343.tif 000076
2017084343.tif 000077
2017084343.tif 000078
2017084343.tif 000079
2017084343.tif 000080
2017084343.tif 000081
2017084343.tif 000082
2017084343.tif 000083
2017084343.tif 000084
2017084343.tif 000085
2017084343.tif 000086
2017084343.tif 000087
2017084343.tif 000088
2017084343.tif 000089
2017084343.tif 000090
2017084343.tif 000091
2017084343.tif 000092
2017084343.tif 000093
2017084343.tif 000094
2017084343.tif 000095
2017084343.tif 000096
2017084343.tif 000097
2017084343.tif 000098
2017084343.tif 000099
2017084343.tif 000100
2017084343.tif 000101
2017084343.tif 000102
2017084343.tif 000103