Метод итерации и его применение в вычислительных задачах

·        уточнения корня,

·        оценка погрешности.

Цель первого этапа – найти отрезок [a,b], на котором функция F(x) меняет знак. Если F(x) непрерывна на[a,b], то уравнение (1) имеет хотя бы один корень на этом отрезке, если, к тому же F(x)строго монотонна на[a,b], то корень единственный.

Отделение корней можно провести графически, построив график функции F(x), а можно протабулировать функцию F(x)  на достаточно большом участке числовой прямой с достаточно большим шагом h, т. е. Вычислить значения F(x) начиная с некоторой точки x0, двигаясь вправо с шагом h.

Как только обнаружится пара соседних значений F(xi-1), F(xi), имеющие разные знаки,

F(xi-1) * F(xi) < 0.

Говорят, что удалось отделить отрезок [a,b] =[xi-1,xi], содержащий корень. Уточнение корня проводится подходящим численным методом.

Отделение корней

^ Отделение корней алгебраических 

и трансцендентных уравнений

 

Пусть имеется уравнение вида

 

F(x) = 0,  (2.1)

 

где F(x) — алгебраическая или трансцендентная функция.

Решить такое уравнение - значит установить, имеет ли оно корни, сколько корней, и найти значения корней (либо точно, либо, если это невозможно, то с нужной точностью). Мы ограничимся обсуждением методов поиска лишь действительных корней,  не затрагивая проблему корней комплексных.

Решение указанной задачи в достаточно общем случае начинается с отделения корней, т. е. с установления:

количества корней;

наиболее «тесных» промежутков, каждый из которых содержит только один

Следует отметить, что универсальных приемов решения этой задачи, пригодных для любых уравнений, не существует.

Если бы мы располагали графиком функции F(x), то примерное положение корней уравнения (2.1) было бы очевидным — точки пересечения графика с осью абсцисс. Однако построение графиков функций обычно и начинается с поиска ее нулей, т.е. возникает замкнутый круг.

Тем не менее отделение корней во многих случаях можно произвести графически. Задачу часто удается сильно упростить, заменив уравнение (2.1) равносильным ему уравнением

f1(x)=f2(x)           (2.2)

В этом случае строятся графики функций f1(x) и f2(x), а потом на оси х отмечаются отрезки, локализующие абсциссы точек пересечения этих графиков.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание по курсовой работе

 

1. Схема метода итерации в общем виде.
2. Метод простых итерации решения СЛАУ

• Условие сходимости итерационного процесса
• Приведение системы к виду удобному для проведения итерации
• Для следующей системы выполнить две итерации вручную, составить схему алгоритма, программу, выполнить расчеты на ЭВМ

x1-х2+х3=6

-х1+6х2-х4=4

2х2-4х3-х4=6

Х1-х2+4х4=4

3. Метод последовательных приближений для нелинейного уравнения:

Отделение корней

Условие сходимости в итерационном процессе

Для следующего уравнения 2x=7-х положительный корень отделить графически

Выполнить итерации без ЭВМ

Составить схему алгоритма, выполнить расчеты на ЭВМ, точность ξ=0,1; ξ =0,01

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ручной расчет

Метод простой итерации.

Прежде чем применять метод итераций, необходимо переставить строки исходной системы таким образом, чтобы на диагонали стояли наибольшие по модулю коэффициенты матрицы. Если при этом условие все таки не выполняется, то иногда удается обеспечить сходимость метода с помощью следующего метода.

Пусть дана система Ax = b. Преобразуем ее к виду: x= Qx + c

где Q = E - D•A, c = D•b

Здесь D - некоторая матрица. Нам необходимо подобрать такую матрицу D, чтобы выполнялось условие |Q| < 1.

Чтобы получить |Q| < 1, используем следующий способ.

 

Имеем СЛАУ

A x =b    (1)

Предполагая, что aii ≠ 0 разрешим новое уравнение системы (1) относительно x1, второе – относительно x2,…, n-ое уравнение – относительно xn. В результате получим:

x1=β1 - α12x2 - α13x3 - ... - α1nxn

x2=β2 - α21x1 - α23x3 - ... - α2nxn

xn=βn - αn1xn - αn3x3 - ... - αnn-1xn-1

где βi=bi/aii; αij=aij/aii при i ≠ j; αii=0

Система (2) в матричной форме имеет вид:

x=β - αx

Систему будем решать методом последовательных приближений. Пусть x0=β, тогда:

x1=b - a x0

x2=b - a x1

....

xk+1=b - a xk

Рассмотрим один из способов преобразования системы: Ax=b,   (1).

позволяющий всегда получать сходящийся процесс. Помножим (1) слева на AT: ATAx=ATb или Cx=d,     (2).

где C=ATA; d=ATb.

Систему (2) принято называть нормальной (Такая система получается при использовании МНК).

Нормальная система обладает рядом замечательных свойств:

1) матрица С – симметрическая;

2) все элементы главной  диагонали cij> 0;

3) матрица С - положительно определена.

Умножаем матрицы ATA.

ATA=3;-8;1;5;-8;42;-9;-12;1;-9;17;4;5;-12;4;18

Умножаем матрицы ATb.

ATb=6;26;-18;6

Приведем к виду:

x1=2-2.67x2+0.33x3+1.67x4

x2=0.62-0.19x1-0.21x3-0.29x4

x3=-1.06+0.0588x1-0.53x2+0.24x4

x4=0.33+0.28x1-0.67x2+0.22x3

Покажем вычисления на примере нескольких итераций.

N=1

x1=2 - 0 • (-2.67) - 0 • 0.33 - 0 • 1.67=2

x2=0.62 - 0 • (-0.19) - 0 • (-0.21) - 0 • (-0.29)=0.62

x3=-1.06 - 0 • 0.0588 - 0 • (-0.53) - 0 • 0.24=-1.06

x4=0.33 - 0 • 0.28 - 0 • (-0.67) - 0 • 0.22=0.33

N=2

x1=2 - 0.62 • (-2.67) - (-1.06) • 0.33 - 0.33 • 1.67=3.45

x2=0.62 - 2 • (-0.19) - (-1.06) • (-0.21) - 0.33 • (-0.29)=0.87

x3=-1.06 - 2 • 0.0588 - 0.62 • (-0.53) - 0.33 • 0.24=-0.93

x4=0.33 - 2 • 0.28 - 0.62 • (-0.67) - (-1.06) • 0.22=0.43

Остальные расчеты сведем в таблицу.

 

 

N	x1	x2	x3	x4	e1	e2	e3	e4
0	0	0	0	0
1	2	0.62	-1.06	0.33	2	0.62	1.06	0.33
2	3.45	0.87	-0.93	0.43	1.45	0.25	-0.13	0.0924

 

 

 

 

 

 

 

 

Метод последовательных приближений

Ответ: x = -0.21895867

Найдем корни уравнения:

2x-7-x = 0

Используем для этого Метод итераций.

Одним из наиболее эффективных способов численного решения уравнений является метод итерации. Сущность этого метода заключается в следующем. Пусть дано уравнение f(x)=0.

Заменим его равносильным уравнением x=φ(x).

Выберем начальное приближение корня x0 и подставим его в правую часть уравнения. Тогда получим некоторое число x1=φ(x0).

Подставляя теперь в правую часть вместо x0 число x1 получим число x2=φ(x1). Повторяя этот процесс, будем иметь последовательность чисел xn=φ(xn-1)

Если эта последовательность сходящаяся, то есть существует предел ξ = lim(xn), то переходя к пределу в равенстве и предполагая функцию φ(x) непрерывной найдем lim(xn) = φ(lim(xn-1)), n → ∞ или ξ=φ(ξ).

Таким образом, предел ξ является корнем уравнения и может быть вычислен по формуле с любой степенью точности.

Находим первую производную:

dF/dx = 2x•log(2)-1

Решение.

Представим уравнение в форме:

x = x - λ(2x-7-x)

Найдем максимальное значение производной от функции f(x) = 2x-7-x

y = 2^x*log(2)-1

[-1;5]

Необходимое условие экстремума функции одной переменной.

Уравнение f'0(x*) = 0 - это необходимое условие экстремума функции одной переменной, т.е. в точке x* первая производная функции должна обращаться в нуль. Оно выделяет стационарные точки xс, в которых функция не возрастает и не убывает.

Достаточное условие экстремума функции одной переменной.

Пусть f0(x) дважды дифференцируемая по x, принадлежащему множеству D. Если в точке x* выполняется условие:

f'0(x*) = 0

f''0(x*) > 0

то точка x* является точкой локального (глобального) минимума функции.

Если в точке x* выполняется условие:

f'0(x*) = 0

f''0(x*) < 0

то точка x* - локальный (глобальный) максимум.

Решение.

Находим первую производную функции:

y' = 2x•ln2(2)

Приравниваем ее к нулю:

2x•ln2(2) = 0

Глобальных экстремумов нет

Находим стационарные точки:

Вычисляем значения функции на концах отрезка

f(-1) = -1+32•ln(2)

f(5) = -0.6534

Ответ:

Имеются только локальные экстремумы (на заданном интервале)

fmin = -1+32•ln(2), fmax = -0.65

max(dF/dx = 2x•log(2)-1) ≈ 0

Значение λ = 1/(0) ≈ 0.1

Таким образом, решаем следующее уравнение:

x-0.1(2x-7-x) = 0

Уточним интервалы, в которых будут находиться корни уравнения. Для этого исходный интервал [-1;5] разобьем на 10 под интервалов.

h7 = -1 + 7*(5-(-1))/10 = 3.2

h8 = -1 + (7+1)*(5-(-1))/10 = 3.8

Поскольку F(3.2)*F(3.8)<0, то корень лежит в пределах [3.2;3.8].

Остальные расчеты сведем в таблицу.

N  x  F(x)

1  3.2  -1.0104

 

Ответ: x = -0.21895867; F(x) = -5.922

 

 

 

 

Представление алгоритмов в виде блок-схем

Метод итерации для линейных уравнений

 

Метод последовательных приближений

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1.

Метод итерации для линейных уравнений

#include<iostream>

#include<vector>

#include<cmath>

using namespace std;

int main()

{

    // Считываем размер вводимой матрицы

    int size;

    cin >> size;

        // Будем хранить матрицу в векторе, состоящем из

    // векторов вещественных чисел

    vector <vector <long double> > matrix;

        // Матрица будет иметь размер (size) x (size + 1),

    // c учетом столбца свободных членов   

    matrix.resize (size);

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

    {

        matrix[i].resize (size + 1);

        for (int j = 0; j < size + 1; j++)

        {

            cin >> matrix[i][j];

        }

    }

   // Считываем необходимую точность решения

    long double eps;

    cin >> eps;

    // Введем вектор значений неизвестных на предыдущей итерации,

    // размер которого равен числу строк в матрице, т.е. size,

    // причем согласно методу изначально  заполняем его нулями

    vector <long double> previousVariableValues (size, 0.0);

    // Будем выполнять итерационный процесс до тех пор,

    // пока не будет достигнута  необходимая точность   

    while (true)

    {

        // Введем вектор значений неизвестных  на текущем шаге      

        vector <long double> currentVariableValues (size);

        // Посчитаем значения неизвестных на текущей итерации

        // в соответствии с теоретическими  формулами

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

        {

            // Инициализируем i-ую неизвестную значением

            // свободного члена i-ой строки  матрицы

            currentVariableValues[i] = matrix[i][size];

            // Вычитаем сумму по всем отличным от i-ой неизвестным

            for (int j = 0; j < size; j++)

            {

                if (i != j)

                {

                    currentVariableValues[i] -= matrix[i][j] * previousVariableValues[j];

                }

            }

            // Делим на коэффициент при i-ой  неизвестной

            currentVariableValues[i] /= matrix[i][i];

        }

        // Посчитаем текущую погрешность  относительно предыдущей итерации

        long double error = 0.0;