численный анализ | C++ для приматов

Задача. Метод Эйткена-Стеффенсона (развитие метода простой итерации). Найти решение уравнения [latex]x=\varphi(x)[/latex] методом Эйткена-Стеффенсона, в котором от заданного начального [latex]x_{0}[/latex] три очередных приближения находятся по формулам: [latex]x_{n+1}=\varphi (x_{n})[/latex]; [latex]x_{n+2}=\varphi (x_{n+1})[/latex]; [latex]x_{n+3}=\frac{x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}[/latex]. Процесс продолжается до достижения одного из условий: [latex]\left | x_{n+3}-x_{n+2} \right |<\varepsilon[/latex] или [latex]x_{n}-2x_{n+1}+x_{n+2}=0[/latex].

Решение. В начале мы задаем начальное приближение [latex]x=x_{0}[/latex] и [latex]\varepsilon[/latex]. Нам понадобится цикл с постусловием. Далее вычисляем первое приближение [latex]x_{1}=\varphi (x_{0})[/latex] и второе приближение [latex]x_{2}=\varphi (x_{1})[/latex]. Находим по формуле [latex]x=\frac{x_{0}x_{2}-x_{1}^{2}}{x_{0}-2x_{1}+x_{2}}[/latex]. Далее мы проверяем выполнение условия выхода из цикла: если [latex]\left | x-x_{0} \right |>\varepsilon[/latex] (нужно проверять разность [latex]\left | x-x_{0} \right |>\varepsilon[/latex], а не [latex]\left | x-x_{2} \right |>\varepsilon[/latex]) и [latex]x_{0}-2x_{1}+x_{2}\neq 0[/latex] тогда цикл продолжается, но если хотя бы одно из условий выполнено, то мы получаем, что [latex]x[/latex] — решение уравнения [latex]x=\varphi(x)[/latex].

Данная программа написана для функции [latex]9.2x^{3}+3.3x^{2}+4x-1[/latex].

Тесты:

x	[latex]\varepsilon[/latex]	Корень уравнения	Комментарий
2	0.005	1.99889	Пройден
1	0.00002	0.233905	Пройден
-4	0.0005	-3.99981	Пройден

Код программы:

#include <iostream>
#include <math.h>
using namespace std;

double f(double x)
{
	return 9.2*x*x*x+3.3*x*x+4*x-1; //задаем уравнение
}

double es(double x, double eps) //с помощью метода Эйтнена-Стеффенсона считаем приближения
{
	double x0, x1, x2, d;
	do
	{
		x0=x;
		x1=f(x0);
		x2=f(x1);
		d=x0-2*x1+x2;
		if (d!=0)
		{
			x=(x0*x2-x1*x1)/d;
		}
		else return x;
	}
	while(fabs(x-x0)>eps); //условие окончания подсчета 
	return x;
}

int main() {
	double x, eps;
	cin >> x >> eps;
	cout << es(x, eps);
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

double f(double x)

{

return 9.2*x*x*x+3.3*x*x+4*x-1; //задаем уравнение

}

double es(double x, double eps) //с помощью метода Эйтнена-Стеффенсона считаем приближения

{

double x0, x1, x2, d;

{

x0=x;

x1=f(x0);

x2=f(x1);

d=x0-2*x1+x2;

if (d!=0)

{

x=(x0*x2-x1*x1)/d;

}

else return x;

}

while(fabs(x-x0)>eps); //условие окончания подсчета

return x;

}

int main() {

double x, eps;

cin >> x >> eps;

cout << es(x, eps);

return 0;

}

Код программы можно проверить здесь.

Решение на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	static double f(double x)
	{
	   return 9.2*x*x*x+3.3*x*x+4*x-1; 
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner  in = new Scanner(System.in);
		double x, eps, x0, x1, x2, d;
		x = in.nextDouble();
		eps = in.nextDouble();
		do{
			x0=x;
			x1=f(x0);
			x2=f(x1);
			d=x0-2*x1+x2;
			if (d!=0)
			{
				x=(x0*x2-x1*x1)/d;
			}
			else break;
    	} 	
    	while(Math.abs(x-x0)>eps);
    	System.out.print(x+" "); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

static double f(double x)

{

return 9.2*x*x*x+3.3*x*x+4*x-1;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double x, eps, x0, x1, x2, d;

x = in.nextDouble();

eps = in.nextDouble();

do{

x0=x;

x1=f(x0);

x2=f(x1);

d=x0-2*x1+x2;

if (d!=0)

{

x=(x0*x2-x1*x1)/d;

}

else break;

}

while(Math.abs(x-x0)>eps);

System.out.print(x+" ");

}

Ссылка на решение.

Related Images:

Задача:
Для заданной матрицы [latex]A(n, n)[/latex] найти обратную [latex]A^{-1}[/latex], используя итерационную формулу:
[latex]A_{k}^{-1} = A_{k-1}^{-1}(2E-A A_{k}^{-1}),[/latex] где [latex]E[/latex] — единичная матрица, [latex]A_{0}^{-1} = E[/latex]. Итерационный процесс заканчивается, если для заданной погрешности [latex]\varepsilon[/latex] справедливо:
[latex]\left| det(A A_{k}^{-1})-1 \right| \le \varepsilon[/latex]

Анализ задачи:
Прежде чем приступать к решению средствами языка C++, я создал прототип в системе компьютерной алгебры Wolfram Mathematica, с которым планировал сверяться при тестировании программы. Тем не менее, внимательный анализ показал, что с таким выбором начального приближения процесс уже на пятом шаге в значительной мере расходится даже для матриц размера 2*2. После уточнения условий и анализа дополнительного материала, посвященного методу Ньютона-Шульца, исходное приближение было изменено (по результатам исследования «An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications», Victor Pan, Robert Schreiber, стр. 8):
[latex]A_{0}^{-1} =\frac { A }{ \left\| A \right\|_{1} \left\| A \right\| _{\infty } }[/latex], где [latex]{ \left\| A \right\| }_{ 1 }=\max _{ i }{ \sum _{ j=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } } [/latex], [latex]{ \left\| A \right\| }_{ \infty }=\max _{ j }{ \sum _{ i=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } }[/latex].
Эффективность предложенного подхода иллюстрируют результаты работы прототипа:

Следовательно, из пространства задачи можно переместиться в пространство решения и составить алгоритм реализации предложенного метода на языке C++.

Тесты:

[latex]n[/latex]	[latex]A[/latex]	[latex]A^{-1}[/latex]	Результат
3	1 2 3 5 5 7 11 13 7	-0.964771 0.430661 -0.017183 0.723533 -0.447973 0.137884 0.172358 0.155200 -0.086211	Пройден
2	1 2 2 1	-0.333067 0.666400 0.666400 -0.333067	Пройден
5	1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1	1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1	Пройден
3	1 2 3 4 5 6 7 8 9	Матрица вырождена	Пройден

Программный код:

#include <cstdio>
#include <algorithm>
#include <cmath>
//очистить выделенную память
void clear(double **arr, int n)
{
    for(int i = 0; i < n; i++)
        delete[] arr[i];
    delete[] arr;
}
//создать копию массива
double** clone(double **arr, int n)
{
    double **newArr = new double*[n];
    for(int row = 0; row < n; row++)
    {
        newArr[row] = new double[n];
        for(int col = 0; col < n; col++)
            newArr[row][col] = arr[row][col];
    }
    return newArr;
}
//print the matrix
void show(double **matrix, int n)
{
    for(int row = 0; row < n; row++){
            for(int col = 0; col < n; col++)
                printf("%lf\t", matrix[row][col]);
            printf("\n");
    }
    printf("\n");
}
//матричное умножение матриц
double** matrix_multi(double **A, double **B, int n)
{
    double **result = new double*[n];
    //заполнение нулями
    for(int row = 0; row < n; row++){
        result[row] = new double[n];
        for(int col = 0; col < n; col++){
            result[row][col] = 0;
        }
    }

    for(int row = 0; row < n; row++){
        for(int col = 0; col < n; col++){
            for(int j = 0; j < n; j++){
                result[row][col] += A[row][j] * B[j][col];
            }
        }
    }
    return result;
}
//умножение матрицы на число
void scalar_multi(double **m, int n, double a){
    for(int row = 0; row < n; row++)
        for(int col = 0; col < n; col++){
            m[row][col] *= a;
        }
}
//вычисление суммы двух квадратных матриц
void sum(double **A, double **B, int n)
{
    for(int row = 0; row < n; row++)
        for(int col = 0; col < n; col++)
            A[row][col] += B[row][col];
}

//вычисление определителя
double det(double **matrix, int n) //квадратная матрица размера n*n
{
    double **B = clone(matrix, n);
    //приведение матрицы к верхнетреугольному виду
    for(int step = 0; step < n - 1; step++)
        for(int row = step + 1; row < n; row++)
        {
            double coeff = -B[row][step] / B[step][step]; //метод Гаусса
            for(int col = step; col < n; col++)
                B[row][col] += B[step][col] * coeff;
        }
    //Рассчитать определитель как произведение элементов главной диагонали
    double Det = 1;
    for(int i = 0; i < n; i++)
        Det *= B[i][i];
    //Очистить память
    clear(B, n);
    return Det;
}

int main()
{
    //Исходная матрица, динамический двухмерный массив
    int n; scanf("%d", &n);
    double **A = new double*[n];
    for(int row = 0; row < n; row++)
    {
        A[row] = new double[n];
            for(int col = 0; col < n; col++)
                scanf("%lf", &A[row][col]);
    }

    /* Численное вычисление обратной матрицы по методу Ньютона-Шульца
        1. Записать начальное приближение [Pan, Schreiber]:
            1) Транспонировать данную матрицу
            2) Нормировать по столбцам и строкам
        2. Повторять процесс до достижения заданной точности.
    */

    double N1 = 0, Ninf = 0; //норма матрицы по столбцам и по строкам
    double **A0 = clone(A, n);       //инициализация начального приближения
    for(size_t row = 0; row < n; row++){
        double colsum = 0, rowsum = 0;
        for(size_t col = 0; col < n; col++){
            rowsum += fabs(A0[row][col]);
            colsum += fabs(A0[col][row]);
        }
        N1 = std::max(colsum, N1);
        Ninf = std::max(rowsum, Ninf);
    }
    //транспонирование
    for(size_t row = 0; row < n - 1; row++){
        for(size_t col = row + 1; col < n; col++)
            std::swap(A0[col][row], A0[row][col]);
    }
    scalar_multi(A0, n, (1 / (N1 * Ninf))); //нормирование матрицы
    //инициализация удвоенной единичной матрицы нужного размера
    double **E2 = new double*[n];
    for(int row = 0; row < n; row++)
    {
        E2[row] = new double[n];
            for(int col = 0; col < n; col++){
                if(row == col)
                    E2[row][col] = 2;
                else
                    E2[row][col] = 0;
            }
    }
    double **inv = clone(A0, n); //A_{0}
    double EPS = 0.001;   //погрешность
    if(det(A, n) != 0){ //если матрица не вырождена
        while(fabs(det(matrix_multi(A, inv, n), n) - 1) >= EPS) //пока |det(A * A[k](^-1)) - 1| >= EPS
        {
            double **prev = clone(inv, n); //A[k-1]
            inv = matrix_multi(A, prev, n);   //A.(A[k-1]^(-1))
            scalar_multi(inv, n, -1);         //-A.(A[k-1]^(-1))
            sum(inv, E2, n);                   //2E - A.(A[k-1]^(-1))
            inv = matrix_multi(prev, inv, n); //(A[k-1]^(-1)).(2E - A.(A[k-1]^(-1)))
            clear(prev, n);
        }
        //вывод матрицы на экран
        show(inv, n);
    }
    else
        printf("Impossible\n");
    clear(A, n);
    clear(E2, n);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

#include <cstdio>

#include <algorithm>

#include <cmath>

//очистить выделенную память

void clear(double **arr, int n)

{

for(int i = 0; i < n; i++)

delete[] arr[i];

delete[] arr;

}

//создать копию массива

double** clone(double **arr, int n)

{

double **newArr = new double*[n];

for(int row = 0; row < n; row++)

{

newArr[row] = new double[n];

for(int col = 0; col < n; col++)

newArr[row][col] = arr[row][col];

}

return newArr;

}

//print the matrix

void show(double **matrix, int n)

{

for(int row = 0; row < n; row++){

for(int col = 0; col < n; col++)

printf("%lf\t", matrix[row][col]);

printf("\n");

}

printf("\n");

}

//матричное умножение матриц

double** matrix_multi(double **A, double **B, int n)

{

double **result = new double*[n];

//заполнение нулями

for(int row = 0; row < n; row++){

result[row] = new double[n];

for(int col = 0; col < n; col++){

result[row][col] = 0;

}

for(int row = 0; row < n; row++){

for(int col = 0; col < n; col++){

for(int j = 0; j < n; j++){

result[row][col] += A[row][j] * B[j][col];

}

return result;

}

//умножение матрицы на число

void scalar_multi(double **m, int n, double a){

for(int row = 0; row < n; row++)

for(int col = 0; col < n; col++){

m[row][col] *= a;

}

//вычисление суммы двух квадратных матриц

void sum(double **A, double **B, int n)

{

for(int row = 0; row < n; row++)

for(int col = 0; col < n; col++)

A[row][col] += B[row][col];

}

//вычисление определителя

double det(double **matrix, int n) //квадратная матрица размера n*n

{

double **B = clone(matrix, n);

//приведение матрицы к верхнетреугольному виду

for(int step = 0; step < n - 1; step++)

for(int row = step + 1; row < n; row++)

{

double coeff = -B[row][step] / B[step][step]; //метод Гаусса

for(int col = step; col < n; col++)

B[row][col] += B[step][col] * coeff;

}

//Рассчитать определитель как произведение элементов главной диагонали

double Det = 1;

for(int i = 0; i < n; i++)

Det *= B[i][i];

//Очистить память

clear(B, n);

return Det;

}

int main()

{

//Исходная матрица, динамический двухмерный массив

int n; scanf("%d", &n);

double **A = new double*[n];

for(int row = 0; row < n; row++)

{

A[row] = new double[n];

for(int col = 0; col < n; col++)

scanf("%lf", &A[row][col]);

}

/* Численное вычисление обратной матрицы по методу Ньютона-Шульца

1. Записать начальное приближение [Pan, Schreiber]:

1) Транспонировать данную матрицу

2) Нормировать по столбцам и строкам

2. Повторять процесс до достижения заданной точности.

double N1 = 0, Ninf = 0; //норма матрицы по столбцам и по строкам

double **A0 = clone(A, n); //инициализация начального приближения

for(size_t row = 0; row < n; row++){

double colsum = 0, rowsum = 0;

for(size_t col = 0; col < n; col++){

rowsum += fabs(A0[row][col]);

colsum += fabs(A0[col][row]);

}

N1 = std::max(colsum, N1);

Ninf = std::max(rowsum, Ninf);

}

//транспонирование

for(size_t row = 0; row < n - 1; row++){

for(size_t col = row + 1; col < n; col++)

std::swap(A0[col][row], A0[row][col]);

}

scalar_multi(A0, n, (1 / (N1 * Ninf))); //нормирование матрицы

//инициализация удвоенной единичной матрицы нужного размера

double **E2 = new double*[n];

for(int row = 0; row < n; row++)

{

E2[row] = new double[n];

for(int col = 0; col < n; col++){

if(row == col)

E2[row][col] = 2;

else

E2[row][col] = 0;

}

double **inv = clone(A0, n); //A_{0}

double EPS = 0.001; //погрешность

if(det(A, n) != 0){ //если матрица не вырождена

while(fabs(det(matrix_multi(A, inv, n), n) - 1) >= EPS) //пока |det(A * A[k](^-1)) - 1| >= EPS

{

double **prev = clone(inv, n); //A[k-1]

inv = matrix_multi(A, prev, n); //A.(A[k-1]^(-1))

scalar_multi(inv, n, -1); //-A.(A[k-1]^(-1))

sum(inv, E2, n); //2E - A.(A[k-1]^(-1))

inv = matrix_multi(prev, inv, n); //(A[k-1]^(-1)).(2E - A.(A[k-1]^(-1)))

clear(prev, n);

}

//вывод матрицы на экран

show(inv, n);

}

else

printf("Impossible\n");

clear(A, n);

clear(E2, n);

return 0;

}

Программа доступна для тестирования по ссылке: http://ideone.com/7YphoX.

Алгоритм решения
При решении данной задачи оправдывает себя подход «разделяй и властвуй»: вычисление обратной матрицы подразумевает промежуточные этапы, корректной реализации которых следует уделить особое внимание. Наверняка стоило бы написать класс matrix и реализовать перегрузку операций, но задачу можно решить и без применения объектно-ориентированных средств, пусть от этого решение и потеряет в изящности.
Можно выделить следующие подзадачи:

Инициализация динамического двухмерного массива и передача его в функцию.
Вычисление определителя матрицы (с применением метода Гаусса).
Вычисление нормы матрицы.
Транспонирование матрицы.
Умножение матрицы на скаляр.
Матричное умножение матриц.
Сложение двух матриц.
Непосредственно итерационный процесс Ньютона-Шульца

Ниже приведено пояснение к подходу к реализации некоторых подзадач:

Выделение памяти для хранения массива происходит не на этапе запуска программы, после компиляции. Для инициализации использован конструктор new
Вычисление определителя можно разбить на два последовательных шага:
1. Приведение матрицы к верхнетреугольному виду (методом Гаусса).
2. Вычисление определителя как произведения элементов главной диагонали.
Нормы матрицы вычисляются как максимальные значения суммы элементов по столбцам и строкам соответственно.
При транспонировании обмениваются местами элементы, симметричные главной диагонали.
При умножении матрицы на скаляр каждый элемент матрицы умножается на соответствующее вещественное число.
При перемножении двух квадратных матриц используется промежуточный массив для хранения результата вычислений.
Сложение двух матриц аналогично попарному сложению элементов, расположенных на соответствующих позициях.
Максимально допустимая погрешность для метода Ньютона-Шульца [latex]\varepsilon = 0.001[/latex]. Программа использует локальный массив для хранения [latex]A_{k}^{-1}[/latex], инициализация которого происходит в теле цикла.

Технические детали реализации:
При выполнении подзадач часто приходится использовать локальные массивы, так что для очистки выделенной под них памяти создана отдельная функция clear().