Méthode de Newton en C ++, Python, Go (pour comprendre les objets de fonction)

Aperçu

Récemment, je vois souvent des implémentations de passer des objets de fonction comme des arguments aux fonctions de rappel en C ++, et je suis toujours confus, donc j'aimerais implémenter quelque chose moi-même et le corriger dans mon esprit. Cette fois, j'ai choisi la méthode Newton comme simple formule de calcul. Implémentez la méthode Newton en C ++, Python, Go en utilisant des objets fonction.

Public cible

• Programmeur C ++
• Programmeur Python --Go programmeur
• Des personnes qui comprennent les bases de la programmation

Objet de fonction

Un objet fonction est tout objet pour lequel un opérateur d'appel de fonction est défini. De cppreference

Des articles comme celui ci-dessous expliquent également les objets de fonction et les fonctions de rappel. Développement en ligne des pointeurs de fonction et des objets de fonction Série présentant la petite technologie C ++ [Astuces C ++ 9 fois au total] # 3

Détails

Méthode Newton

La méthode Newton est une méthode qui permet de trouver une solution même pour une équation non linéaire par calcul numérique. Un algorithme qui trouve une ligne tangente à partir de la valeur initiale X1 et effectue un calcul itératif tout en mettant à jour X à l'intersection de la ligne tangente et de l'axe X.

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

S'il s'agit d'une équation linéaire, la solution de l'équation peut être résolue immédiatement en utilisant la constante de proportionnalité. Avec la formule ci-dessous, vous pouvez voir rapidement que la solution est $ x = - \ frac {1} {2} $.

f(x) = 2x + 1

Alors qu'en est-il de la formule ci-dessous?

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

Si l'équation peut être bien transformée et peut être faite comme $ (x-a) (x-b) (x-c) $, une solution peut être obtenue même avec une équation non linéaire. Cela n'est pas possible avec des équations non linéaires réelles (par exemple, des équations de diffusion géothermique, des calculs de turbulence, etc.). Dans un tel cas, il existe la méthode Newton pour effectuer avec force des calculs itératifs pour trouver une solution. L'équation de la méthode Newton est la suivante.

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

Je pense que la méthode Newton est souvent écrite dans les classes de programmation des universités. Ce n'est pas une formule difficile, il est donc facile de commencer.

Dans cet article également, j'ai choisi la méthode Newton simple pour apprendre tout en écrivant moi-même l'objet fonction.

Let's implémentation

Interface de base

1. 1. Créez des objets fonction pour f (x) et df (x).
2. Passez l'objet fonction créé dans la fonction Newton, la valeur initiale de X, le nombre maximal d'essais et la condition de convergence comme arguments.

• Cette fois, lorsque la valeur initiale est x = 0, 2, 3, le nombre maximum d'essais est de 1000,

3. 3. Implémentez le polynôme suivant avec la fonction Newton. Implémentez une boucle infinie et terminez le calcul lorsque la différence entre $ x_ {n + 1} $ et $ x_n $ est inférieure à $ 1,0 × 10 ^ {-10} $. De plus, le calcul s'arrête même lorsque le nombre maximum d'essais est atteint.

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

4. Reçoit la valeur de retour de la fonction Newton et affiche le résultat.

C++

1. 1. Créez des objets fonction pour f (x) et df (x).

En C ++, nous avons utilisé std :: pow pour implémenter le cube de X. Dans ce cas, la formule n'est pas telle qu'elle est, et je pense qu'elle n'est pas lisible.

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. Passez l'objet fonction créé dans la fonction Newton, la valeur initiale de X, le nombre maximal d'essais et la condition de convergence comme arguments.

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. Implémentez le polynôme suivant avec la fonction Newton. Implémenter en boucle infinie pour que le calcul se termine avec la condition de convergence et le nombre maximum d'essais.

En définissant l'opérateur () dans la classe Calc,

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. Reçoit la valeur de retour de la fonction Newton et affiche le résultat.

Python

1. 1. Créez des objets fonction pour f (x) et df (x).

main.py

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

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

2. Passez l'objet fonction créé dans la fonction Newton, la valeur initiale de X, le nombre maximal d'essais et la condition de convergence comme arguments.

Dans 1, seule la définition a été faite dans main.py. La fonction définie est transmise en tant qu'objet fonction ci-dessous.

main.py

    newton = formula.newton_func(f, df)

Le nombre maximal d'essais et la condition de convergence n'ont pas été transmis en tant qu'arguments, mais transformés en variables membres de la classe Calc.

calc.py

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

3. 3. Implémentez le polynôme suivant avec la fonction Newton. Implémenter en boucle infinie pour que le calcul se termine avec la condition de convergence et le nombre maximum d'essais.

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. Reçoit la valeur de retour de la fonction Newton et affiche le résultat.

Go

1. 1. Créez des objets fonction pour f (x) et df (x).

Je ne pouvais pas implémenter un cube avec `` x ** 3 '' comme Python.

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
}

Comme indiqué ci-dessous, la méthode de retour de l'objet fonction dans la fonction principale et de le passer en tant qu'argument à la fonction Newton n'a pas pu être correctement implémentée. Il est plus intuitif et facile à comprendre s'il est défini et implémenté comme ci-dessus. S'il vous plaît laissez-moi savoir si vous êtes gentil 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. Passez l'objet fonction créé dans la fonction Newton, la valeur initiale de X, le nombre maximal d'essais et la condition de convergence comme arguments.

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. Implémentez le polynôme suivant avec la fonction Newton. Implémenter en boucle infinie pour que le calcul se termine avec la condition de convergence et le nombre maximum d'essais.

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. Reçoit la valeur de retour de la fonction Newton et affiche le résultat.

Résumé

Je pense qu'il est essentiel pour les débutants de s'évader en maîtrisant les objets fonctionnels et les fermetures. Apprenons en utilisant lambda et la fermeture pour des réponses telles que AtCoder. Merci d'avoir lu jusqu'au bout. La qualité du code n'est pas bonne, veuillez donc commenter si vous le souhaitez.

J'ajouterai std :: bind plus tard.