Метод итерации и его применение в вычислительных задачах
Министерство образования и науки РФ
ФБГОУ ВПО «Дагестанский государственный технический университет»
Кафедра: “Прикладной математики и информатики”.
Курсовая работа
по дисциплине «Методы вычислений»
На тему:
«Метод итерации и его применение в вычислительных задачах.»
Выполнил:
студент 3-го курса
Балахаев Ф.С.
Проверила:
Алиосманова О.А
Каспийск 2014 г.
Аннотация
В данной работе рассмотрены метод итерации и его применение в вычислительных задачах. В рамках курсовой работы реализованы на языке блок-схем алгоритмы и программа на языке программирования С++.
Кроме этого, наши вычисления производятся в среде: Excel и расписаны вручную.
Курсовая работа содержит:
• 2 приложения
• 28 страниц
Содержание
Введение…………………………………………………………
Теоретические сведения……………………………………...……….4
Решение нелинейных уравнений……………………………………..8
Задание по курсовой работе……………………………………....…11
Ручной расчет…………………………………………………….…..
Метод последовательных приближений...................
Представление алгоритмов в виде блок-схем………………..….....17
- пример 1…………………………….........17
- пример 2………………………….........…18
Приложение 1………………………………………………...........
Приложение 2………………………………………………………....23
Результаты полученные на ЭВМ…………………………….......…..25
- пример 1……………………….................25
- пример 2…………………...…......…........25
Заключение……………………………………………………
Литература……………………………………………………
Введение
В данной курсовой работе необходимо рассмотреть один из множества существующих итерационных методов, метод простой итерации для решения систем линейных алгебраических уравнений.
Прежде чем говорить о вышеуказанном методе, я дам краткую характеристику вообще итерационным методам.
Итерационные методы дают возможность найти решение системы, как предел бесконечного вычислительного процесса, позволяющего по уже найденным приближениям к решению построить следующее, более точное приближение. Привлекательной чертой таких методов является их самоисправляемость и простота реализации на ЭВМ. Если в точных методах ошибка в вычислениях, когда она не компенсируется случайно другими ошибками, неизбежно ведет к ошибкам в результате, то в случае сходящегося итерационного процесса ошибка в каком-то приближении исправляется в последующих вычислениях, и такое исправление требует, как правило, только нескольких лишних шагов единообразных вычислений. Итерационный метод, для того чтобы начать по нему вычисления, требует знания одного или нескольких начальных приближений к решению.
Условия и скорость сходимости каждого итерационного процесса существенно зависят от свойств уравнений, то есть от свойств матрицы системы, и от выбора начальных приближений.
Теоретические сведения
Исследовать метод простой итерации для решения систем линейных алгебраических уравнений, а именно: влияние способа перехода от системы 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.), то говорят, что итерационный процесс сходится.
Итак, численные методы решения нелинейного уравнения состоят из трех этапов:
· отделение корня,
· уточнения корня,
· оценка погрешности.
Цель первого этапа – найти отрезок [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), а потом на оси х отмечаются отрезки, локализующие абсциссы точек пересечения этих графиков.
Задание по курсовой работе
- Схема метода итерации в общем виде.
- Метод простых итерации решения СЛАУ
- Условие сходимости итерационного процесса
- Приведение системы к виду удобному для проведения итерации
- Для следующей системы выполнить две итерации вручную, составить схему алгоритма, программу, выполнить расчеты на ЭВМ
x1-х2+х3=6
-х1+6х2-х4=4
2х2-4х3-х4=6
Х1-х2+4х4=4
- Метод последовательных приближений для нелинейного уравнения:
Отделение корней
Условие сходимости в итерационном процессе
Для следующего уравнения 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;-
Умножаем матрицы 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.24x
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;
- Метод итераций и метод Зейделя
- Методи управління організацією
- Методи управління підприеством
- Методи формування ціни на підприємстві
- Методи функціонування валютного ринку
- Методи функціонування валютного ринку
- Методи ціноутворення
- Методи та инструменти тотального управлиння якистю
- Методи та матеріали, польових та лабораторних досліджень
- Методи та прийоми аудиту та їх застосування під час отримання аудиторських доказів
- Методи та прийоми навчання письма на початковому етапі вивчення німецької мови
- Методи та способи відображення цифрових графічних зображень в системі Win32
- Методи та технології соціальної роботи з дітьми-вулиці
- Методи та умови ціноутворення в міжнародній торгівлі
