Newtons Methode in C ++, Python, Go (zum Verständnis von Funktionsobjekten)

Überblick

In letzter Zeit sehe ich Implementierungen wie das Übergeben eines Funktionsobjekts häufig als Argument einer Rückruffunktion in C ++, und ich bin immer noch verwirrt. Daher möchte ich etwas selbst implementieren und es in meinem Kopf beheben. Dieses Mal habe ich die Newton-Methode als einfache Berechnungsformel gewählt. Implementieren Sie die Newton-Methode in C ++, Python, Go mithilfe von Funktionsobjekten.

Zielgruppe

• C ++ - Programmierer
• Python-Programmierer
• Zum Programmierer gehen
• Personen, die die Grundlagen der Programmierung verstehen

Funktionsobjekt

Ein Funktionsobjekt ist ein Objekt, für das ein Funktionsaufrufoperator definiert ist. Von cppreference

Artikel wie der folgende erläutern auch Funktionsobjekte und Rückruffunktionen. Inline-Erweiterung von Funktionszeigern und Funktionsobjekten Serie zur Einführung der kleinen C ++ - Technologie [Tipps für C ++ insgesamt 9 Mal] # 3

Einzelheiten

Newton-Methode

Die Newton-Methode ist eine Methode, die auch für eine nichtlineare Gleichung durch numerische Berechnung eine Lösung finden kann. Ein Algorithmus, der eine Tangentenlinie aus dem Anfangswert X1 findet und eine iterative Berechnung durchführt, während X am Schnittpunkt der Tangentenlinie und der X-Achse aktualisiert wird.

Bild https://linky-juku.com/linear-programming/

Wenn es sich um eine lineare Gleichung handelt, kann die Lösung der Gleichung sofort unter Verwendung der Proportionalitätskonstante beantwortet werden. Mit der folgenden Formel können Sie schnell erkennen, dass die Lösung $ x = - \ frac {1} {2} $ lautet.

f(x) = 2x + 1

Was ist also mit der folgenden Formel?

f(x) = x^3 - 5x + 1

Wenn die Gleichung gut transformiert werden kann und wie $ (x-a) (x-b) (x-c) $ gemacht werden kann, kann eine Lösung auch mit einer nichtlinearen Gleichung erhalten werden. Dies ist mit tatsächlichen nichtlinearen Gleichungen (z. B. geothermische Diffusionsgleichungen, Turbulenzberechnungen usw.) nicht möglich. In einem solchen Fall gibt es die Newton-Methode, um iterative Berechnungen zwangsweise durchzuführen, um eine Lösung zu finden. Die Gleichung der Newton-Methode lautet wie folgt.

x_{n+1}=x_n−\frac{f(x_n)}{f′(x_n)}

Ich denke, dass die Newton-Methode oft in Programmierkursen an Universitäten geschrieben wird. Es ist keine schwierige Formel, daher ist es einfach, loszulegen.

Auch in diesem Artikel habe ich die einfache Newton-Methode gewählt, um beim Schreiben von Funktionsobjekten selbst zu lernen.

Lassen Sie uns implementieren

Grundlegende Schnittstelle

1. 1. Erstellen Sie Funktionsobjekte für f (x) und df (x).
2. Übergeben Sie das in der Newton-Funktion erstellte Funktionsobjekt, den Anfangswert von X, die maximale Anzahl von Versuchen und die Konvergenzbedingung als Argumente.

• Dieses Mal, wenn der Anfangswert x = 0, 2, 3 ist, beträgt die maximale Anzahl von Versuchen 1000,

3. 3. Implementieren Sie das folgende Polynom mit der Newton-Funktion. Implementieren Sie in einer Endlosschleife und beenden Sie die Berechnung, wenn die Differenz zwischen $ x_ {n + 1} $ und $ x_n $ weniger als $ 1.0 × 10 ^ {-10} $ beträgt. Darüber hinaus endet die Berechnung auch dann, wenn die maximale Anzahl von Versuchen erreicht ist.

x_{n+1}=x_n−\frac{f(x_n)}{f′(x_n)}

4. Erhält den Rückgabewert der Newton-Funktion und zeigt das Ergebnis an.

C++

1. 1. Erstellen Sie Funktionsobjekte für f (x) und df (x).

In C ++ haben wir std :: pow verwendet, um den Würfel von X zu implementieren. In diesem Fall ist die Formel nicht so wie sie ist, und ich denke, sie ist nicht lesbar.

Main.cpp

double fx(double x)
{
    return std::pow(x, 3.0) - 5 * x + 1;
}

double df(double x)
{
    return 3 * std::pow(x, 2) - 5;
}

2. Übergeben Sie das in der Newton-Funktion erstellte Funktionsobjekt, den Anfangswert von X, die maximale Anzahl von Versuchen und die Konvergenzbedingung als Argumente.

Main.cpp

    Calc calc;
    std::function<double(std::function<double(double)>,
                         std::function<double(double)>,
                         double,
                         int,
                         double)> newton = calc;

    std::cout << "Newton Object : " <<newton(fx, df, 2, Calc::MAX_ITER, Calc::EPC) << std::endl;
    std::cout << "Newton Object : " <<newton(fx, df, 0, Calc::MAX_ITER, Calc::EPC) << std::endl;
    std::cout << "Newton Object : " <<newton(fx, df, 3, Calc::MAX_ITER, Calc::EPC) << std::endl;

Main.cpp

    std::function<double(std::function<double(double)>,
                         std::function<double(double)>,
                         double,
                         int,
                         double)> newton_ptr = Newton_Main;

    std::cout << "Newton Ptr : " << newton_ptr(fx, df, 2, Calc::MAX_ITER, Calc::EPC) << std::endl;
    std::cout << "Newton Ptr : " << newton_ptr(fx, df, 0, Calc::MAX_ITER, Calc::EPC) << std::endl;
    std::cout << "Newton Ptr : " << newton_ptr(fx, df, 3, Calc::MAX_ITER, Calc::EPC) << std::endl;

3. 3. Implementieren Sie das folgende Polynom mit der Newton-Funktion. Implementieren Sie in einer Endlosschleife, sodass die Berechnung mit der Konvergenzbedingung und der maximalen Anzahl von Versuchen endet.

Durch Definieren des Operators () in der Calc-Klasse

Calc.cpp

double Calc::operator()(std::function<double(double)>f, std::function<double(double)>df, double x0, int max_iter, double epc)
{
    double x = x0;
    int iter = 0;
    while(1)
    {
        xNew_ = x - f(x)/df(x);
        if (std::abs(x - xNew_) < epc)
        {
            break;
        }
        x = xNew_;
        iter ++;
        if (iter == max_iter)
        {
            break;
        }
    }
    return xNew_;
}

Main.cpp

double Newton_Main(std::function<double(double)>f, std::function<double(double)>df, double x0, int max_iter, double epc)
{
    double xNew = 0;
    double x = x0;
    int iter = 0;
    while(1)
    {
        xNew = x - f(x)/df(x);
        if (std::abs(x - xNew) < epc)
        {
            break;
        }
        x = xNew;
        iter ++;
        if (iter == max_iter)
        {
            break;
        }
    }
    return xNew;
}

4. Erhält den Rückgabewert der Newton-Funktion und zeigt das Ergebnis an.

Python

1. 1. Erstellen Sie Funktionsobjekte für f (x) und df (x).

main.py

def f(x):
    return x**3 - 5*x + 1

def df(x):
    return 3*x**2 - 5

2. Übergeben Sie das in der Newton-Funktion erstellte Funktionsobjekt, den Anfangswert von X, die maximale Anzahl von Versuchen und die Konvergenzbedingung als Argumente.

In 1 wurde nur die Definition in main.py vorgenommen. Die definierte Funktion wird unten als Funktionsobjekt übergeben.

main.py

    newton = formula.newton_func(f, df)

Die maximale Anzahl von Versuchen und die Konvergenzbedingung wurden nicht als Argumente übergeben, sondern in Mitgliedsvariablen der Calc-Klasse umgewandelt.

calc.py

    def __init__(self):
        self.eps = 1e-10
        self.max_iter = 1000

3. 3. Implementieren Sie das folgende Polynom mit der Newton-Funktion. Implementieren Sie in einer Endlosschleife, sodass die Berechnung mit der Konvergenzbedingung und der maximalen Anzahl von Versuchen endet.

calc.py

    def newton_func(self, f, df):
        def newton(x0):
            x = x0
            iter = 0
            while True:
                x_new = x - f(x)/df(x)
                if abs(x-x_new) < self.eps:
                    break
                x = x_new
                iter += 1
                if iter == self.max_iter:
                    break
            return x_new
        return newton

4. Erhält den Rückgabewert der Newton-Funktion und zeigt das Ergebnis an.

Go

1. 1. Erstellen Sie Funktionsobjekte für f (x) und df (x).

Ich konnte Cube mit `` `x ** 3``` wie Python nicht implementieren.

main.go

// Calc Newton Calculaion struct
type Calc struct{}

// fx f(x) formula
func (calc Calc) fx(x float64) float64 {
	return x*x*x - 5*x + 1
}

// df differentiated f(x)
func (calc Calc) df(x float64) float64 {
	return 3*x*x - 5
}

Wie unten gezeigt, konnte die Methode zum Zurückgeben des Funktionsobjekts in der Hauptfunktion und zum Übergeben als Argument an die Newton-Funktion nicht gut implementiert werden. Es ist intuitiver und leichter zu verstehen, wenn es wie oben definiert und implementiert wird. Bitte lassen Sie mich wissen, wenn Sie nett sind m (_ _) m

main.go

type Calc struct{}

func (calc Calc) fx(x float64) func() float64 {
	return func() float64 {
		return x*x*x - 5*x + 1
	}
}

func (calc Calc) df(x float64) func() float64 {
	return func() float64 {
		return 3*x*x - 5
	}
}

2. Übergeben Sie das in der Newton-Funktion erstellte Funktionsobjekt, den Anfangswert von X, die maximale Anzahl von Versuchen und die Konvergenzbedingung als Argumente.

main.go

func main() {
	calc := Calc{}

	var ans float64

	ans = calc.Newton_main(calc.fx, calc.df, 2, 1000, 1e-10)
	fmt.Println("The answer is : ", ans)

	ans = calc.Newton_main(calc.fx, calc.df, 0, 1000, 1e-10)
	fmt.Println("The answer is : ", ans)

	ans = calc.Newton_main(calc.fx, calc.df, 3, 1000, 1e-10)
	fmt.Println("The answer is : ", ans)
}

3. 3. Implementieren Sie das folgende Polynom mit der Newton-Funktion. Implementieren Sie in einer Endlosschleife, sodass die Berechnung mit der Konvergenzbedingung und der maximalen Anzahl von Versuchen endet.

main.go

// Newton_main Calculation for Newton method
func (calc Calc) Newton_main(fx func(float64) float64, df func(float64) float64, x0 float64, maxIter int, epc float64) float64 {
	var xNew float64
	var x = x0
	var iter int
	for {
		xNew = x - fx(x)/df(x)
		if math.Abs(x-xNew) < epc {
			break
		}
		x = xNew
		iter++
		if iter == maxIter {
			break
		}
	}
	return xNew
}

4. Erhält den Rückgabewert der Newton-Funktion und zeigt das Ergebnis an.

Zusammenfassung

Ich denke, es ist für Anfänger wichtig zu entkommen, indem sie Funktionsobjekte und Verschlüsse beherrschen. Lassen Sie uns lernen, während Sie Lambda und Closure für Antworten wie AtCoder verwenden. Vielen Dank für das Lesen bis zum Ende. Die Qualität des Codes ist nicht gut, bitte kommentieren Sie, wenn Sie möchten.

Ich werde später std :: bind hinzufügen.