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

                Министерство образования и науки РФ

ФБГОУ ВПО «Дагестанский государственный технический университет»

 

Кафедра: “Прикладной математики и информатики”.

 

 

Курсовая работа

по дисциплине «Методы вычислений»

На тему:

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

 

 

 

         Выполнил:

      студент 3-го курса

               Балахаев Ф.С.

        Проверила:

                        Алиосманова О.А

 

 

 

Каспийск 2014 г.

Аннотация

 

В данной  работе рассмотрены метод итерации и его применение в вычислительных задачах. В рамках курсовой работы реализованы на языке блок-схем алгоритмы и программа на языке программирования С++.

Кроме этого, наши вычисления производятся в среде: Excel и расписаны вручную.

 

Курсовая работа содержит:

• 2 приложения

• 28 страниц

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

Введение……………………………………………………………......3

Теоретические сведения……………………………………...……….4

Решение нелинейных уравнений……………………………………..8

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

Ручной расчет…………………………………………………….…..12

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

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

• пример 1…………………………….........17
• пример 2………………………….........…18

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

Приложение 2………………………………………………………....23

Результаты полученные на ЭВМ…………………………….......…..25

• пример 1……………………….................25
• пример 2…………………...…......…........25

Заключение……………………………………………………....……26

Литература…………………………………………………………….27

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теоретические сведения

Исследовать метод простой итерации для решения систем линейных алгебраических уравнений, а именно: влияние способа перехода от системы F(x)=x к системе x= (x) на точность полученного решения, скорость сходимости метода, время счета, число операций.

Пусть дана система линейных алгебраических уравнений в виде Ax=b (2.2.1).

Пусть (2.2.1.) приведена каким-либо образом к виду x=Cx+f (2.2.2), где C - некоторая матрица, f - вектор-столбец. Исходя из произвольного вектора

 

x01

x( 0 )= x02

x03

 

строим итерационный процесс x( k+1 )=Cx( k )+f (k=0,1,2,3,…) или в развернутой форме

x1 ( k+1 ) = c11 x1( k ) + c12 x2( k ) + …+ c1n xn( k ) + f1 ,    (2.2.3)

xn ( k+1 ) = cn1 x1( k ) + cn2 x2( k ) + …+ 1nn xn( k ) + fn .

 

Производя итерации, получим последовательность векторов x( 1 ), x( 2),…, x( k ),… Доказано, что если элементы матрицы C удовлетворяют одному из условий

(i=1,2,…,n) (2.2.4)

(j=1,2,…,n) (2.2.5),

 

то процесс итерации сходится к точному решению системы x при любом начальном векторе x(0), то есть

 

x= x(k ) .

 

Таким образом, точное решение системы получается лишь в результате бесконечного процесса, и всякий вектор x(k) из полученной последовательности является приближенным решением. Оценка погрешности этого приближенного решения x(k) дается одной из следующих формул:

 

| xi- xi( k ) | | xi( k ) - xi( k -1 )|, (2.2.4')

 

если выполнено условие (2.2.4), или

 

| xi- xi( k ) | | xi( k ) - xi( k -1 )|, (2.2.5')

 

если выполнено условие (2.2.5). Эти оценки можно еще усилить соответственно так:

 

max | xi- xi( k ) | | xi( k ) - xi( k -1 )|, (2.2.4'')

или

 

| xi- xi( k ) | | xi( k ) - xi( k -1 )|. (2.2.5'')

 

Процесс итераций заканчивают, когда указанные оценки свидетельствуют о достижении заданной точности.

Начальный вектор x( 0 ) может быть выбран, вообще говоря, произвольно. Иногда берут x( 0 )=f. Однако, наиболее целесообразно в качестве компонент вектора x( 0 ) взять приближенные значения неизвестных, полученные грубой прикидкой.

Приведение системы (2.2.1) к виду (2.2.2) можно осуществить различными способами. Важно только, чтобы выполнялось одно из условий (2.2.4) или (2.2.5). Ограничимся рассмотрением двух таких способов.

Первый способ. Если диагональные элементы матрицы А отличны от нуля, то есть

aii 0 ( i=1,2,…,n),

то систему (2.2.1) можно записать в виде

 

x1= (b1 - a12 x2 - … - a1nxn),

x2= (b2 - a21 x1 - a23 x3 -… - a2nxn),      (2.2.6)

xn= (bn - an1 x1 - … - an n-1 xn-1 ).

 

В этом случае элементы матрицы С определяются следующим образом:

 

(i j), cii=0,

и тогда условия (2.2.4) и (2.2.5) соответственно приобретают вид

 

(i=1,2,… ,n), (2.2.7)

(j=1,2,… ,n). (2.2.8)

 

Неравенства (2.2.7), (2.2.8) будут выполнены, если диагональные элементы матрицы А удовлетворяют условию

 

(i=1,2,… ,n), (2.2.9)

 

то есть если модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов (не считая свободных членов).

Второй способ позволяет записать систему (2.2.1) в виде

x1= b1 - (a11 -1)x1 - a12 x2 - … - a1nxn,

x2= b2 - a21 x1 -(a22 -1)x2 -… - a2nxn,      (2.2.10)

xn= bn - an1 x1 - an2 x2 -… -(ann -1)xn.

 

и пояснений не требует.

 

Как правило, процесс решения нелинейного уравнения общего вида: f(х)=0 осуществляется в два этапа. На первом этапе отделяют корни, т. е. находят такие отрезки, внутри которых находится строго один корень. На втором этапе уточняют корень, т.е. находят его значение х* с предварительно заданной точностью e. В практических задачах решением называют любое значение x, отличающееся по модулю от точного значения х* не более чем на величину e.

Идеи аналитических методов первого этапа базируются на очевидном свойстве непрерывных функций: корни функции (точки пересечения f(х) с горизонтальной осью) обязательно лежат между соседними экстремумами функции (хотя обратное неверно: между каждой парой экстремумов необязательно находится корень).

Идеи методов второго этапа можно сгруппировать по трем основным направлениям. В первом – поиск корня с заданной погрешностью сводится к перебору всех возможных значений аргумента с проверкой наличия решения. Во втором – поиск корня нелинейной функции заменяется поиском корня той или иной более простой функции (линейной, параболической), близкой к исходной нелинейной; как правило, процесс поиска осуществляется итерационными процедурами (однотипными, последовательно повторяющимися). В третьем – нелинейное уравнение вида: f(x)=0 сводят к одной из форм вида: g(х) = j(х) и стремятся обеспечить равенство левой и правой частей тоже, как правило, с помощью итерационных процедур.

 

 

Условием окончания процесса решения уравнения (т.е. получения корня x* с заданной погрешностью) может быть одно из двух возможных: 1) |f(х)|<=d, 2) |х*–хk|<=e, где d, e – предварительно заданные малые величины, k – номер итерации, т.е. или близость к нулю левой части уравнения, или близость друг к другу двух значений х, между которыми находится решение. Второе условие во многих случаях можно использовать, не зная точного значения корня, путем замены его другим, например: |хk+1–хk|<=e, при выполнении которого данное условие будет гарантированно выполняться. Условие окончания поиска выбирается исходя из неформальных соображений, и в некоторых случаях применение разных условий может привести к существенно разным результатам. При решении конкретных задач в математическом моделировании важными являются две цели решения:

1) обеспечение близости  к нулю f(x) (f(х)»0) как меры выполнения тех или иных балансовых соотношений, тогда не очень важно, при каких именно (в пределах здравого смысла конкретной прикладной задачи) значениях х это равенство справедливо с заданной погрешностью;

2) обеспечение точности  нахождения решения х*, имеющего содержательное значение, при этом f(х)»0 является лишь индикатором правильности решения. Отсюда и выбирают условие окончания поиска решения.

Знание особенностей левой части нелинейного уравнения позволяет в ряде случаев, не производя отделения корней, определить число корней (причем отдельно действительных и комплексных), что невозможно в общем случае, а также предельные оценки корней, интервалы существования корней. Это, прежде всего, касается алгебраических уравнений с действительными коэффициентами (далее для простоты – алгебраических), часто встречающихся в практике. Такие уравнения имеют вид:

 

 

Кроме того, с учетом конкретного вида уравнения можно построить более эффективные алгоритмы

Отделение корней может производиться графически (путем построения графика функции f(x)) или аналитически. Для аналитического отделения корней находят все критические точки функции f(х), т. е. точки, в которых производные равны нулю или не существуют. Это можно сделать численными методами или – в несложных случаях – аналитически. Для этого f(х) дифференцируют, приравнивают производную к нулю и решают полученное уравнение относительно х. Кроме того, определяют все точки, где по тем или иным причинам (например, знаменатель обращается в нуль, под логарифмом появляется нуль и т. д.) производная может не существовать. В этих (критических) точках или в непосредственной близости от них определяют знак функции f(хi), т. е. находят sign f(хi). Затем строят ряд знаков функции в критических точках, включая в рассмотрение и крайние точки числовой оси -¥ и +¥. Анализируют этот ряд, и по числу смен знаков определяют количество корней (равно числу смен знаков sign f(хi)) и интервалы, где локализованы эти корни. На левой и на правой границах такого интервала функция f(х) должна иметь разные знаки. В случае необходимости можно дополнительно к критическим точкам использовать и произвольные точки, что позволяет сузить интервал локализации корня. Особенно это надо делать, когда одна из границ интервала находится в бесконечности, так как интервал хотя бы с одной границей в бесконечности не позволит уточнить корни.

 

Решение нелинейных уравнений

Задача нахождения корней нелинейных уравнений вида

F(x)=0        (1)

встречается в различных областях научных исследований. (здесь F(x) – некоторая непрерывная функция).

Нелинейные уравнения делятся на два класса – алгебраические и трансцендентные. Алгебраическими уравнениями называются уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, многочлен является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и др.) называются трансцендентными.

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

Однако встречающиеся на практике уравнения не удается решить такими простыми методами. Для их решения используются итерационные методы.

Итерационные методы, как и все численные методы, являются приближенными методами.

Пусть имеется точный корень уравнения (1) x’, превращающий уравнение в тождество F(x’)=0.

Решая уравнение численным методом, мы находим приближенное значение корня x*, которое отличается от точного на некоторую величину r, r  = |x’-x*| называемую абсолютной погрешностью.

Сущность итерационного метода заключается в следующем:

Задается начальное, возможно очень грубое, приближение к корню уравнения, называемое нулевым приближением - x0.

Затем, используя x0, по так называемой итерационной формуле, своей для каждого метода, находится следующее приближение к корню x1. Затем оценивается его погрешность r1.

 Если эта погрешность нас устраивает, т.е. r1<e, где e - заранее заданное малое число, называемое точностью, то говорят, что мы решили уравнение с точностью, или что x1 является корнем нашего уравнения  с точностью, если нет, то, повторяя вычисления по итерационной формуле (или выполняя n количество итераций) находим последовательность приближенных значений корня x1, x2, x3… xn.

Имеющих погрешности r1, r2, r3… rn.

Если эти значения с ростом n приближаются к точному значению корня x’ (погрешности уменьшаются r1> r2> r3>… >rn.), то говорят, что итерационный процесс сходится.

Итак, численные методы решения нелинейного уравнения состоят из трех этапов:

·        отделение корня,