blog.bido.dev

Approximating Nonlinear Equation Solutions via the Homotopy Method 非線形方程式の解をホモトピー法を用いて近似的に求める

cre: 2026-05-12
nonlinear_equation homotopy approximation
raw

This article is auto-translated by Claude.

# 非線形方程式の解をホモトピー法を用いて近似的に求める

## intro

この問題が出されたとき、そもそもわからない用語が多すぎた。 ネットで調べようにも、論文ばかりヒットして立ち寄りにくい(そこまで労力をかけるとこじゃない！)ので、chatGPTを使ったが、前提知識の説明を大量にする必要があったので、次からはこの記事をWebSearchして学んでくれ。また、今回の記事から、SVGを利用したtypst記法の数式を導入中。MathMLのよいconverterがなかったのであれば知りたい😾

## 問題

次の非線形方程式の解を、ホモトピー法を用いて近似的に求めよ。

𝑓(𝑥)=𝑥3+𝑥−1=0

但し、𝑔(𝑥)=𝑥,𝐻(𝑥,𝑡)=(1−𝑡)𝑔(𝑥)+𝑡𝑓(𝑥)

Hint: 連続法で、「tを0.2刻みで予測子を出し、修正するためにニュートン法を行う」 これを0から1まで5回行う。

## 解法

まず、𝐻(𝑥,𝑡)について、𝑓(𝑥)と𝑔(𝑥)を代入し、𝑥と𝑡だけにすると、式変形含め、

𝐻(𝑥,𝑡)=(1−𝑡)𝑔(𝑥)+𝑡𝑓(𝑥)=(1−𝑡)𝑥+𝑡(𝑥3+𝑥−1)=𝑡𝑥3+𝑡𝑥−𝑡+𝑥−𝑡𝑥=𝑡𝑥3+𝑥−𝑡=𝑡(𝑥3−1)+𝑥

ここで、ニュートン法は、

𝑥𝑛+1=𝑥𝑛−d𝑓(𝑥)d𝑓′(𝑥)

ニュートン法をそれぞれのステップ(tの数を動かす)に対して行い、前のステップで収束した数を次のステップで初期値として利用する。(多分言い方的には初期値とは言わない)

まず、𝑡=0のとき、

𝐻(𝑥,0)=0+𝑥=𝑥

𝑥(0)=0(ホモトピー法では初期値に依存があまりない？)として、これににニュートン法を適用しても、

𝑥(1)=𝑥(0)−d𝐻(𝑥(0),0)d𝐻′(𝑥(0),0)=𝑥(0)−d(0(𝑥3(0)−1)+𝑥(0))d(1)=𝑥(0)−𝑥(0)=0

である。 次に、𝑡=0.2のときを考える。

𝑥(2)=𝑥(1)−d𝐻(𝑥(1),𝑡)d𝐻′(𝑥(1),𝑡)=𝑥(1)−d(𝑡(𝑥3(1)−1)+𝑥(1))d(3𝑥2(1)𝑡+1)=0−0.2×(03−1)+03×02×0.2+1=0.2

このニュートン法を行うと、数回で0.2程度に収束するので、目標の誤差になるまでニュートン法をし続ければ良い。 この、tを変化させる&そのtでニュートン法を行うをする。 これは面倒なのでプログラムにした。

fn main() {
    let mut x:f64 = 0.0;//初期値
    let expected_deviation:f64 = 0.01;//期待する精度

    // steps
    for i in 1..=5 {
        let t = (i as f64/ 5.0) as f64;
        let mut loop_counter = 0;
        println!("===step {}===",i);
        loop {
            loop_counter += 1;
            let x2 = x - (t * x * x * x + x - t)/(3.0 * t * x * x + 1.0);
            println!("value calculating: {}",x2);
            //期待する誤差以下になれば終了
            if (x2 - x).abs() <= expected_deviation {
                println!("value: {}",x);
                break;
            }else {
                x = x2;
            }
        }
        println!("t: {}, x: {} loop:{}\n",t,x,loop_counter);
    }
}

出力(syntax highlightはbashにした、色がいいね)

===step 1===
value calculating: 0.2
value calculating: 0.19843750000000002
value: 0.2
t: 0.2, x: 0.2 loop:2

===step 2===
value calculating: 0.38778625954198476
value calculating: 0.37837284868992194
value: 0.38778625954198476
t: 0.4, x: 0.38778625954198476 loop:2

===step 3===
value calculating: 0.5272587331955364
value calculating: 0.517124090388034
value calculating: 0.5170587075724934
value: 0.517124090388034
t: 0.6, x: 0.517124090388034 loop:3

===step 4===
value calculating: 0.6220366200432104
value calculating: 0.6144747259172406
value: 0.6220366200432104
t: 0.8, x: 0.6220366200432104 loop:2

===step 5===
value calculating: 0.6855685277361753
value calculating: 0.682336752364747
value: 0.6855685277361753
t: 1, x: 0.6855685277361753 loop:2

## outro

理解が深まれば追記します。

# Approximating Nonlinear Equation Solutions via the Homotopy Method

## intro

When this problem was assigned, I didn't understand most of the terminology. Searching online only turned up papers — too much effort for the occasion. I ended up using ChatGPT, but had to explain a lot of background first. Use this article for WebSearch next time. Also, starting with this post, I'm introducing math typeset with typst via SVG. If you know a good MathML converter, let me know 😾

## problem

Find the solution of the following nonlinear equation approximately using the homotopy method.

𝑓(𝑥)=𝑥3+𝑥−1=0

where 𝑔(𝑥)=𝑥,𝐻(𝑥,𝑡)=(1−𝑡)𝑔(𝑥)+𝑡𝑓(𝑥)

Hint: Using the continuation method, generate a predictor at t-steps of 0.2, then apply Newton's method as a corrector. Repeat from t=0 to t=1 (5 steps total).

## solution

First, substituting 𝑓(𝑥) and 𝑔(𝑥) into 𝐻(𝑥,𝑡) and simplifying to only 𝑥 and 𝑡:

𝐻(𝑥,𝑡)=(1−𝑡)𝑔(𝑥)+𝑡𝑓(𝑥)=(1−𝑡)𝑥+𝑡(𝑥3+𝑥−1)=𝑡𝑥3+𝑡𝑥−𝑡+𝑥−𝑡𝑥=𝑡𝑥3+𝑥−𝑡=𝑡(𝑥3−1)+𝑥

Newton's method is:

𝑥𝑛+1=𝑥𝑛−d𝑓(𝑥)d𝑓′(𝑥)

Apply Newton's method at each t-step, using the previous step's converged value as the starting point.

First, when 𝑡=0:

𝐻(𝑥,0)=0+𝑥=𝑥

Setting 𝑥(0)=0 (homotopy methods are relatively insensitive to the initial guess?), Newton's method gives:

𝑥(1)=𝑥(0)−d𝐻(𝑥(0),0)d𝐻′(𝑥(0),0)=𝑥(0)−d(0(𝑥3(0)−1)+𝑥(0))d(1)=𝑥(0)−𝑥(0)=0

Next, consider 𝑡=0.2:

𝑥(2)=𝑥(1)−d𝐻(𝑥(1),𝑡)d𝐻′(𝑥(1),𝑡)=𝑥(1)−d(𝑡(𝑥3(1)−1)+𝑥(1))d(3𝑥2(1)𝑡+1)=0−0.2×(03−1)+03×02×0.2+1=0.2

Applying Newton's method here converges to approximately 0.2 after a few iterations. We repeat: advance t, apply Newton's method at that t. This gets tedious by hand, so I wrote a program:

fn main() {
    let mut x:f64 = 0.0;//初期値
    let expected_deviation:f64 = 0.01;//期待する精度

    // steps
    for i in 1..=5 {
        let t = (i as f64/ 5.0) as f64;
        let mut loop_counter = 0;
        println!("===step {}===",i);
        loop {
            loop_counter += 1;
            let x2 = x - (t * x * x * x + x - t)/(3.0 * t * x * x + 1.0);
            println!("value calculating: {}",x2);
            //期待する誤差以下になれば終了
            if (x2 - x).abs() <= expected_deviation {
                println!("value: {}",x);
                break;
            }else {
                x = x2;
            }
        }
        println!("t: {}, x: {} loop:{}\n",t,x,loop_counter);
    }
}

Output (syntax-highlighted as bash — the colors look good)

===step 1===
value calculating: 0.2
value calculating: 0.19843750000000002
value: 0.2
t: 0.2, x: 0.2 loop:2

===step 2===
value calculating: 0.38778625954198476
value calculating: 0.37837284868992194
value: 0.38778625954198476
t: 0.4, x: 0.38778625954198476 loop:2

===step 3===
value calculating: 0.5272587331955364
value calculating: 0.517124090388034
value calculating: 0.5170587075724934
value: 0.517124090388034
t: 0.6, x: 0.517124090388034 loop:3

===step 4===
value calculating: 0.6220366200432104
value calculating: 0.6144747259172406
value: 0.6220366200432104
t: 0.8, x: 0.6220366200432104 loop:2

===step 5===
value calculating: 0.6855685277361753
value calculating: 0.682336752364747
value: 0.6855685277361753
t: 1, x: 0.6855685277361753 loop:2

## outro

I'll add more as my understanding deepens.