Численные методы решения уравнений на ЭВМ Исполнитель
- Скачано: 31
- Размер: 819.85 Kb
Численные методы решения уравнений на ЭВМ
Введение.
Вычисление значений функции по заданной формуле чаще всего встречается среди математических операций. Первая встреча, это вычисление числовых значений алгебраического выражения. Также при построении графиков функций вычисляем значении функции по заданным аргументам. Каждая прикладная задача требует знания каких-то величин, которые получаются путём вычисления значений функции по формуле. Для многих функций можно пользоваться готовыми таблицами. Однако, сколько бы ни было составлено таких таблиц, всегда будут возникать новые функции и необходимость их табулирования.
Задача табулирования функции, то есть выполнения вычислений по данной формуле, и будет первой задачей. С вычислениями по готовым формулам связан вопрос о точности вычислений. Для осуществления этих задач необходимо объединить все вычисления в расчётной рабочей таблице. Единый рецепт для составления таблицы трудно указать. Можно привести несколько общих соображений. Таблица должна быть составлена так, что в каждом столбце выполнялись однообразные действия. Столбцы располагаются в таком порядке, чтобы результаты, полученные в одном столбце, использовались при вычислении значений для следующего. Рекомендуется заполнять таблицу столбец за столбцом. Так как при заполнении одного столбца мы выполняем только однотипные операции, и, это ускорит вычисления, также облегчит контроль над вычислениями: благодаря монотонности изменения результатов отдельные ошибки (просчёты) могут быть легко обнаружены.
Пример 1.
Мощность электрического тока, даваемого батареей, выражается формулой:
(1)
где - мощность в ваттах, Е - Э.Д.С. в вольтах, r – внутреннее сопротивление батареи;R – сопротивление внешней цепи в омах.
Полагая Е = 10 В. , r = 0,56 Ом, составим таблицу 1 значений , как функции R для промежутка изменений последнего с интервалами по R в 1 Ом.
Нужные окончательные результаты вычислений содержатся в столбцах (1) – значения независимой переменной R и в столбце (5)- значение функции . В заголовке столбца (5) показано, что для нахождения его значений нужно: значения из столбца (2) делить на значения из столбца (4). Аналогично можно было написать (4)=(3), показывая, что для получения значений столбца (4) нужно значения из столбца (3) возводить в квадрат. Для заполнения столбца (4) необходимо выяснить, сколько цифр после запятой нужно вписать в эту графу. Такой же вопрос возникает и при заполнении столбца (5). Прежде всего, следует отметить, что в формулу (1) входят: константы Е = 10 В. , r = 0, 5 Ом ; поэтому нужно выяснить характер этих констант. Если эти величины являются приближенными, то выписывать в столбцах (4) и (5) большое число знаков не имеет смысла. Но, даже если считать значения Е и r абсолютно точными (что мало вероятно), всё равно нет необходимости выписывать четыре знака в графе (4), если требуется, например: найти значение с точностью до одной сотой. Для выяснения необходимого числа знаков в промежуточных вычислениях следует рассмотреть вопрос о точности арифметических действий.
Пока до рассмотрения этого вопроса будем считать значения Е и r точными и сохранять в столбце (4) все четыре знака после запятой. При этом в столбце (5) можно считать верным третий знак после запятой.
Форма расчётной таблицы 1 зависит от того, какими вычислительными средствами мы располагаем. Схема таблицы 1 удобна при производстве вычислений из клавишной вычислительной машине с автоматическим делением. Если деление придется выполнять без помощи вычислительных машин, то есть возможность воспользоваться таблицами обратных величин, то в таблице 1 удобно ввести столбец вида и получать значения вместо деления умножения значений из этого столбца, на значения из столбца (2).
Таким образом, вычисления по формуле (1) будут иметь вид таблицы1.
Таблица 1.
| R | 100R | R+r | (R+r) | |
| (1) | (2) | (3) | (4) | (5) |
|
1 2 3 4 5 6 7 8 9 10 |
100 200 300 400 500 600 700 800 900 1000 |
1,57 2,57 3,57 4,57 5,57 6,57 7,57 8,57 9,57 10,57 |
2,4649 6,6049 12,7419 20,8849 31,0249 43,1649 57,3049 73,4449 91,5849 111,7249 |
40,570 30,281 23,539 19,153 16,116 13,900 12,215 10,893 9,827 8,951 |
{spoiler=Подробнее}
Значения , полученные в столбце (5) таблицы 2, являются приближенными, потому что точное деление невозможно.
к сказанному выше примыкают часто возникающие в практике вопросы следующего характера. Предположим, что радиус круга r измерен с некоторой ошибкой. Как оценить ошибку величины площади круга, вычисленной по формуле ?
Иногда необходимо решать и обратную задачу: задаётся величина допустимой ошибки для площади круга; требуется определить, с какой точностью следует измерять её радиус.
Если величину площади круга нужно иметь с небольшой точностью, то нет смысла измерять его радиус с большой точностью.
В общей постановке эти задачи формулируются так:
Задача 1:
Прямая задача:
независимое переменное ‘’ известно с некоторой точностью, с какой точностью можно найти значение функции
и аналогично формулируется
обратная задача:
если необходимо получить значение функции с заданной точностью, то какова должна быть точность значений независимой переменной ?
Для решения этих задач нам необходимо познакомиться с приближёнными числами и способами их записи.
1 Приближенные числа и погрешности.
Пусть - некоторая величина, истинное значение которой известно или неизвестно. Число , которое мы находим с помощью измерения величины , мы будем называть приближённым значением величины или приближённым числом.
Число a называют приближённым значением по недостатку, если оно меньше истинного значения, и по избытку, если оно больше.
Число 3,14 является приближённым значением числа π по недостатку, а 2,72- приближённым значением числа e по избытку.
Абсолютная погрешность приближённого числа есть величина
Так как не всегда истинное значение величины неизвестно, неизвестной остаётся и абсолютная погрешность. Вместо неё приходится рассматривать предельную абсолютную погрешность, которая означает число, не меньшее абсолютной погрешности. Иногда предельную абсолютную погрешность называют просто абсолютная погрешность.
Принято записывать приближённые числа таким образом, чтобы вид числа показывал его абсолютную погрешность, которая не должна превосходить половины единицы последнего разряда, сохраняемого при записи.
Запись 3,1416 означает, что абсолютная погрешность этого приближённого числа не превосходит 0,00005. Для числа 370 абсолютная погрешность не превосходит 0,5. Если это число должно имеет большую точность, например, если абсолютная погрешность меньше 0,05, то следует писать не 370, а 370,0.
Пример: Указать степень точности приближённых чисел 37∙10; 370; 370,0; 370,00.
Их предельные абсолютные погрешности составляют ответственно 5; 0,5; 0,05; 0,005.
Число двести семьдесят пять тысяч с абсолютной погрешностью, не превосходящей 500, надо писать в виде 275∙103. Если написать 275000, то предельная абсолютная погрешность будет равна 0,5.
При наличии большого количества цифр число следует округлять, отбрасывая излишние цифры следующим образом: если первая цифра отброшенных цифр 4 или меньше, то последняя оставшаяся цифра сохраняется без изменения, если первая из отброшенных цифр 5 или больше, то последняя оставшаяся цифра увеличивается на единицу.
Исключением из этого правила является случай, когда отбрасывается только пятёрка или же пятёрка с нулями. Принято сохранять последнюю цифру без изменения, если она чётная, и увеличивать её на единицу до чётной, если она была нечётной.
Точность данного приближённого числа не характеризируется его абсолютной погрешностью.
Действительно, погрешность в 0,5м слишком велика при измерении в комнате, допустима при измерении садового участка, и не может быть замечена при измерении расстояния между городами.
Настоящим показателем точности результата измерения или вычисления является его относительная погрешность.
Относительной погрешностью приближённого значения величины называют абсолютную величину отношения его абсолютной погрешности к истинному значению этой величины. Она часто выражается в процентах.
Так как истинное значение величины обычно неизвестно, при определении относительной погрешности, вместо истинного значения величины берут приближённое значение величины.
Эта замена обычно не отражается на величине относительной погрешности ввиду близости этих значений и малости абсолютной погрешности.
Пример 1
π=3,14. Предельная абсолютная погрешность составляет 0,0016, а относительная -0,00051 или 0,051% - это процентная погрешность.
Выше была сформулирована Задача 1: прямая и обратная задача.
Решение этих задач даётся следующей основной теоремой.
Теорема:
Предельная абсолютная погрешность функции равна произведению абсолютной величины её производной на предельную абсолютную погрешность аргумента
Доказательство: Δx = 0 или Δx > 0
X = x + Δx
Ввиду малости мы можем заменить приращение функции её дифференциалом. Тогда получим из , что
Здесь
Следовательно,
- предельная погрешность аргумента
Тогда предельная абсолютная погрешность функции можно принять равной
.
Теорема доказана.
x- предельная относительная погрешность аргумента
y- предельная относительная погрешность функции
из того, что
эту формулу можно использовать для нахождения относительных погрешностей конкретных функций, например: тогда
Пусть теперь , тогда из , находим x;
Пример 2: Определим предельную относительную погрешность площади круга, вычисляемой по формуле S=πr2 ; Из yx следует s r=2r ;
Таким образом, относительная погрешность вычисленной площади вдвое больше относительной погрешности измеренного радиуса.
Пример 3:
Определим, с какой относительной погрешностью может быть найдена сторона квадрата, если известна, что его площадь равна S=12,34 см2 .
Решение:
Из выражения площади видно, что она дана с предельной абсолютной погрешностью 0,005 см2 , откуда следует, что ее относительная погрешность
s =.
Так как сторона квадрата , то из yx находим,
а s = s=0,0002 (=,02%)
Приведем без доказательство:
1.Предельная абсолютная погрешность суммы равна сумме предельных абсолютных погрешностей слагаемых.
2.Относительная погрешность суммы слагаемых одного знака заключена между наименьшей и наибольшей относительными погрешностями слагаемых.
3.Предельная относительная погрешность произведения равна сумме предельных относительных погрешностей сомножителей.
4.Предельная относительная погрешность частного равна сумме предельных относительных погрешностей делимого и делителя.
Правила
- При сложении и вычитании абсолютные погрешности складываются.
- При умножении и делении относительные погрешности складываются; при возведении в степень относительные погрешности умножаются на абсолютную величину показателя степени.
- При нахождении значения функции абсолютная погрешность функции равна произведению абсолютной погрешности аргумента на абсолютную величину производной.
Заметим ещё, что при вычислении значений функций абсолютная погрешность может существенным образом зависеть от того, каким образом записана расчётная формула и каково расположение операций в этой формуле.
Для пояснения рассмотрим следующий пример.
Пример 4:
Вычислим площадь кругового кольца с внутренним радиусом r=1,750 и толщиной h=0,005.
Здесь вычисления можно производить по формулам:
2 -2 и
Хотя алгебраически эти формулы тождественны, но для вычисления вторая во много раз лучше первой, так как при вычитании близких величин в первой формуле относительная погрешность сильно возрастает.
Совет:
Формулы для вычисления надо стараться преобразовывать к такому виду, чтобы в них не было вычитания близких величин.
Вычитание близких величин может привести к большой потере точности и большим относительным ошибкам.
Таким образом, мы изложим только один вопрос: как, зная погрешность исходных данных, оценить погрешность результата расчёта!
Вопрос о методах оценки погрешностей исходных данных, возникающих в процессе измерения, изучает теория ошибок измерения.
2 Метод Гаусса для решения систем линейных алгебраических уравнений.
Рассмотрим для простоты систему линейных алгебраических уравнений четвёртого порядка
(1)
-коэффициента будем называть ведущим элементом первой строки. Предположим, что он не равен нулю. Разделив первое уравнения системы (1) на , получим следующую новое уравнение
(2)
где
Исключаем неизвестную из каждого уравнения системы (1), начиная со второго, путем вычитания уравнения (2), умноженного на коэффициент при в соответствующем уравнении
1)
Обозначая
получаем вместо второго уравнения системы (1) следующее уравнение
2)
Обозначая
,
получаем вместо третьего уравнения системы (1) следующее уравнение
3)
Обозначая
получаем вместо четвёртого уравнения системы (1) следующее уравнение
Таким образом, получим следующую систему
(3)
Допустим, что ведущий элемент второй строки, т.е. коэффициент тоже отличен от нуля. Тогда, разделив на него второе из уравнений (3), получим
(4)
где
Исключив с помощью уравнения (4) неизвестную из двух последних уравнений в (3), приходим к системе уравнений
(5)
где
Если ведущий элемент третьей строки не равен нулю, то, поделив на него третье из уравнений (5) и вычтя найденное уравнение, умноженное на , из четвёртого уравнения, получим
(6)
где
Наконец, если , то разделив на него четвёртое уравнение системы (6), придем к системе уравнений
(7)
где
Из системы (7) неизвестные находятся явно в обратном порядке по формулам
(8)
Процесс приведения системы (1) к треугольному виду (7) называется прямым ходом, а нахождение неизвестных по формулам (8) – обратным ходом метода Гаусса. Решение системы (1) по изложенному методу Гаусса при ручном счете обычно представляется в виде таблице 1.Последний столбец в таблице введен для контроля вычислений, осуществляемого следующим образом. Задаем равным сумме остальных элементов i-ой строки, взятой с обратным знаком, т.е.
Тогда сумма всех элементов каждой из четырёх расширенных начальных строк будет равна нулю. Затем в процессе исключения неизвестных производим над элементами последнего столбца те же самые действия, что и над элементами соответствующих строк, а именно, полагаем
(9)
где
При этом сумма элементов вновь получаемых расширенных строк должна оставаться равной нулю, поскольку эти элементы находятся с помощью линейных операций над предыдущими строками.
Аналогично, методом Гаусса решается система линейных алгебраических уравнений любого порядка
(1*)
Если а также ведущие элементы остальных строк, получаемые в процессе вычислений, отличны от нуля, то система (1*) приводится к треугольному виду
(7*)
Ведущие элементы и коэффициенты системы (7*) находятся с помощью формул:
(9*)
где
Обратный ход, в котором в обратном порядке определяются неизвестные, осуществляются по формулам:
(8*)
Подсчёт числа выполняемых арифметических действий
Лемма 1
(11)
Подсчитаем число выполняемых арифметических действий при решении системы порядка и без учёта операций контроля.
При исключении неизвестной осуществляются следующие действия:
а). n-операций, при делении членов левой и правой части первого уравнения, кроме первого члена правой части.
б). расходуются n умножений и n вычитаний при исключении из второго и последующих уравнений, число которых равно n-1
Таким образом, общее число арифметических действий, затрачиваемых на исключение , есть
(12)
При исключении производятся совершенно аналогичные вычисления, как и при исключении . Разница в том, что осуществляются действия над строками матрицы, размеры которой в каждом направлении на единицу меньше.
Поэтому
Вообще
Всего в прямом ходе затрачивается число арифметических действий, равное
Отсюда, полагая, чтои из леммы 1 находим
(13)
В обратном ходе число умножений и вычитаний, вместе взятых, равно удвоенному числу элементов квадратной матрицы порядка n, расположенных под главной диагональю, и, как показывают простые подсчёты, составляет
(14)
(15)
Вычисление определений:
(16)
Схема с выбором главного элемента.
Если в прямом ходе решения систем уравнений схемой единственного деления окажется ведущий элемент какой-либо строки, равным нулю, то изложенный простейший вариант метод Гаусса непригоден для решения соответствующей системы или вычисления определителя, заданная система уравнений может иметь единственное решение.
Кроме того, если определитель системы не равен нулю, но в процессе вычислений встречаются ведущие элементы, которые достаточно малы по сравнению с другими элементами соответствующих строк, то это обстоятельство способствует усилению отрицательного влияния погрешностей округления на точность результата.
Изложим схему, называемую схемой с выбором главного элемента, которое в случае, когда определитель системы отличен от нуля, при отсутствии погрешностей округления всегда приводит к единственному решению и менее чувствительна к погрешностям округления.
Пусть, как и прежде, дана система (1*). Сначала добиваемся выполнения условий
путём перестановки в случае необходимости двух уравнений системы(1*), а также двух столбцов неизвестных со своими коэффициентами, и соответствующей перенумерации коэффициентов и неизвестных. Найденный максимальный по модулю коэффициент, обозначенный при перенумерации через , называется первым главным элементом. Затем, разделив на , первое уравнение и исключив из остальных (n-1) уравнений получаем (7*), далее с уравнениями системы (7*), кроме первого, поступаем аналогично, как и со всей системой (1*) и обеспечиваем выполнение неравенств
При этом, если переставлялись столбцы неизвестных, то соответствующая перестановка производится и в первом уравнении системы (7*). Найденный максимальный по модулю коэффициент, обозначенный через , называется вторым главным элементом и т.д.
Если определитель системы (1*) отличен от нуля, то в прямом ходе будет получена система вида (7*).
Обратный ход выполняется по формулам (8*). Переходя к первоначальной нумерации теперь уже найденных неизвестных, получаем решение заданной системы (1*)
Таблица 1.
|
1
|
|||||
| 1 | |||||
| 1 | |||||
| 1 | |||||
| 1 | |||||
| 1 | |||||
| 1 |
Пример 1. Используя схему Гаусса, решить систему уравнений с точностью 0,001.
|
2 4 1 3 |
3 2 3 1 |
6 1 1 1 |
1 2 1 6 |
2 3 -1 4 |
14 12 5 15 |
:2 |
|
1
|
1,5 -4 1,5 -3,5 |
3 -11 -2 -8 |
0,5 0 0,5 4,5 |
1 -1 -2 1 |
7 -16 -2 -6 |
*4*1*3 :(-4) |
| 1 |
1,5 1 |
3 2,75 -6,125 1,625 |
0,5 0 0,5 4,5 |
1 0,25 -2,375 1,875 |
7 4 -8 8 |
*1,5*(-2)*0,5 :(-6,125) |
| 1 |
1,5 1 |
3 2,75 1
|
0,5 0 -0,0816 4,6326 |
1 0,25 0,3878 1,2448 |
7 4 1,3061 5,8776 |
*1,625 :4,6326 |
| 1 |
1,5 1 |
3 2,75 1
|
0,5 0 -0,0816 1 |
1 0,25 0,3878 0,2687 |
7 4 1,3061 1,2688 |
|
| 0,95 | -0,877 | 0,41 | 0,27 | |||
П Р О Г Р А М М А П А С К А Л Ь
ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ.
uses crt;
type
mat = array [1..20,1..21] of real;
vec = array [1..20] of real;
var a:mat;
x:vec;
i,n:integer;
s:real;
{------------------------------------------------------------------}
procedure matr(N:integer; Var a:mat); {procedure of data input}
var i,j:integer;
begin for i:=1 to n do
for j:=1 to n+1 do
begin
write ('A',I:2,J:2,'?');
readln(a[i,j]);
end;
writeln (' ');
end;
{------------------------------------------------------------------}
procedure Gauss (N:integer; var a:mat; var x:vec; var s:real);
var
i,j,k,l,k1,n1,key:integer;
r:real;
{perestanovka elementov matricy - vybor max diagonalnogo elementa}
begin
n1:=n+1;
for k:= 1 to n do
begin k1:=k+1;
s:=a[k,k];
j:=k;
for i:=k1 to n do
begin r:=A[i,k];
if ABS(r)>ABS(s) then
begin s:=r;
j:=i;
end;
end;
if s=0.0 then exit;
if j<>k then
for i:=k to n1 do
begin r:=A[k,i];
A[k,i]:=A[j,i];
A[j,i]:=r;
end;
if key<>1 then
begin
for i:=1 to n do
for j:=1 to n1 do
begin write (a[i,j]:4:2,' ');
if j=n1 then writeln (' ');
end;
end;
key:=1; writeln (' ');
for j:=k1 to n1 do
A[k,j]:=A[k,j]/s;
for i:=k1 to n do
begin r:=A[i,k];
for j:=k1 to n1 do
A[i,j]:=A[i,j]-A[k,j]*r;
end;
end;
if s<>0.0 then
for i:=n downto 1 do
begin s:=a[i,n1];
for j:=i+1 to n do
s:=s-a[i,j]*x[j];
x[i]:=s;
end;
end;
{------------------------------------------------------------------}
begin
clrscr;
repeat write ('N?');readln (n);
matr(n,a);
Gauss(n,A,X,S);
if s<>0.0 then
for i:=1 to n do
writeln('x',i:2,'=',x[i]:4:2,' ')
else writeln('Det=0');
readln;
clrscr;
until false
end.
ТЕСТОВЫЕ ПРИМЕРЫ
Пример 1.
4.00 6.00 1.00 3.00
1.00 -3.00 2.00 7.00
2.00 1.00 -2.00 -1.00
Ответ:
x 1=1.49
x 2=-0.76
x 3=1.61
Пример 2.
0.68 0.05 -0.11 0.08 2.15
0.21 -0.13 0.27 -0.80 0.44
-0.11 -0.84 0.28 0.06 -0.83
-0.08 0.15 -0.50 -0.12 1.16
Ответ:
x 1=2.83
x 2=-0.33
x 3=-2.71
x 4=-0.67
3 Вещественное линейное пространство
Определение 1
Совокупность элементов образует вещественное линейное пространство, если для любых элементов введены следующие понятия:
Сумма со свойствами:
+ = +
+ =
+
произведения на любое вещественное число со свойствами:
Определение 2
Вещественное линейное пространство называется метрическим, если в нём введено определённым образом понятие расстояния между его элементами – метрика.
Определение 3
Скалярную неотрицательную величину называют метрикой пространства , если для любых
Выполняется:
= для
Определение 4
Вещественное линейное пространство называется нормированным, если каждому элементу поставлено в соответствие неотрицательное число и называемой нормой, удовлетворяющее условиям:
В линейном нормированном пространстве метрику вводят как норму разности между элементами:
Виды наиболее употребительных норм:
М- норма
Последовательность элементов пространства называется сходящийся к элементу , если из того, что , следует существование такого , что
Нормированное пространство называется полным, если каждая последовательностьсходится. Полное нормирование пространства называется Банаховым или В-пространством.
Приведём определение 5 основных норм в пространствах векторов и матриц.
Если в пространстве векторов
Введена норма , то согласованной с ней нормой в пространстве матриц называют норму :
Рассмотрим нормы вектора :
Согласованные с ними нормы в пространстве матриц следующие:
где собственные значения матрицы
матрица, сопряжённая с матрицей .
4 Метод простой итерации решения систем
линейных уравнений.
Простейшим итерационным методом решения систем линейных уравнений:
или в матричном виде:
где
является метод простой итерации.
Система уравнений (2) преобразуется к виду:
(3)
где
(4)
Итерационный процесс записывается в виде :
, (5)
Для сходимости метода простых итераций при любом начальном приближении итерационного процесса (5) необходимо и достаточно, чтобы все собственные значения матрицы были по модулю меньше единицы.
Поскольку это условие связано с необходимостью решения уравнения :
,
Что в общем случае приводит к громоздким вычислениям, на практике применяется более удобный достаточный признак сходимости, связанный с понятием нормы матрицы.
Теорема о достаточном условии сходимости метода простой итерации:
Если то система уравнений (3) имеет единственное решение и итерационный процесс (5) сходится к решению со скоростью геометрической прогрессии.
Доказательство:
Применяя систему уравнений (3) неравенства треугольника, получим:
отсюда: или .
Следовательно, система уравнений (3) имеет единственное решение.
Обозначим его: . Введём обозначение, . Вычтем из (3)-(5)
Поскольку , очевидно равенство:
По равенству треугольника:
(6)
По условию теоремы: Следовательно, .
Теорема доказана.
Для оценки требуемого количества итераций с целью достижения заданной точности решения можно воспользоваться неравенством (6):
(7).
Вычислительная схема простой итерации:
1). Вычисляем элементы матрицы и вектора по (4).
2) Вычисляем обозначим
Если то итерационный процесс сходится.
3). В качестве начального приближения выбираем вектор
Обозначим .
Решаем систему уравнений:
Тогда .
4) Вычисляем необходимое количество итераций для достижения требуемой точности решения :
=:
Отсюда:
(8)
5) Реализуем, согласно вычисленному значению , требуемое число итераций.
Пример:
,
т.е.
.
Вычисляем :
Вычисляем :
,
,
= -0,255+0,574= 0,319.
= -0, 5+0,319== - 0,181.
=2 = bx=
= 1+0,275= 1,275
=+
=2 - 0,120=1,880
=3
.
.
=2-0,087=1,923.
= 5 = (1,946+0,362) = 0,288.
x= 1+0,288=1,288.
= (-1,305+0,544) = -0,084.
= 2-0,084=1,916.
= -0,261+ 0,584= 0,323.
= -0, 5+ 0,323= -0,177.
= 6 = (1,916+0,354)=0,284.
=1+0,284=1,284.
=(-1,288+0,531)= -0,084,
=2-0,084= 1,916
= -0,258+0,578=0,320
= -0,5+0,320= -0,180
Полученные значения принимаем за решение системы линейных уравнений с точностью : , , -0,18
П Р О Г Р А М М А П А С К А Л Ь
ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ ПРОСТОЙ ИТЕРАЦИИ.
{cTp. 40}
var p:array [1..9] of real; b,x,e:real;
M,N,K:integer;
function F(x:real):real;
const pi=3.14159265;
var Q,R,S,T:real; K: integer;
begin T:= 2*x/sqrt(pi); s:=T-p[1]; r:=-x*x; K:=1;
repeat Q:=S; T:=T*R/K; S:=s+T/(2*k+1); K:=K+1;
until s=q;
f:=x+b*s;
end;
procedure iter(var b,x,e:real; m:integer; function F:real);
var x1,R:real; i:integer;
begin
for i:=1 to m do
begin
x1:=x; x:=f(x);
if ABS(x-x1)<e then exit;
if i=m then writeln('ITERACII VSE');
end;
end;
begin
repeat write('B,X,E,M?');readln(B,X,E,M);
write('Skolko Parametrov?');readln(n);
for K:=1 to n do begin
write('P(',k:2,')?'); readln(p[k]);
end;
iter (B,X,E,M,F);
writeln('x=',x);
until false
end.
5 Трансцендентные уравнения.
Отделение корней.
Во многих прикладных задачах возникает необходимость решения уравнений вида
(1)
где - заданная функция; - неизвестная величина; параметры задачи.
Как правило, при каждом фиксированном наборе параметров уравнение (1) может иметь конечное, либо бесконечное количество решений , что соответствует определенному физическому смыслу конкретной задачи.
Например, в электродинамике при математическом моделировании электромагнитных волновых колебательных процессов в линиях передачи и резонаторах получают так называемое дисперсионное уравнение вида (1). В этом случае параметрами являются частота колебаний, геометрические параметры системы и включений, пространственное распределение диэлектрической и магнитной проницаемостей в электродинамической структуре и т.д. В качестве неизвестного могут быть выбраны коэффициенты распространения и затухания электромагнитных волн в линиях передачи либо собственные частоты и добротности колебательных систем. Бесконечное множество решений дисперсионного уравнения будет соответствовать бесконечному числу потенциально возможных собственных типов волн (колебаний) в исследуемой системе.
Только в простейших уравнений удается найти решение в аналитическом виде, т.е. записать формулу, выражающую искомую величину , в явном виде через параметры .
В большинстве же случаев приходится решать уравнения вида (1) численными методами.
Численные решения уравнения (1) обычно проводят в два этапа. На первом этапе необходимо отделить корни уравнения, т.е. найти такие интервалы изменения переменной , где расположен только один корень. По сути дела, на этом этапе находят приближенные значения корней с погрешностью, задаваемой длиной каждого интервала. На втором этапе проводят уточнение отделенных корней, т.е. находят корни с заданной точностью.
Рассмотрим табличный способ отделения корней уравнения (1). В интересующей нас области изменения неизвестного при фиксированных параметрах вычислим ряд значений левой части уравнения (1) и результаты поместим в таблицу, по которой можно построить график (рис.1).
|
. . . |
. . . |
Рис.1
С точности до выбранного шага (расстояния между точками ) из графика (таблицы) определяются приближенные значения корней уравнения (1). Уменьшая шаг в окрестности каждого корня, можно повысить точность определения корней.
Если левая часть уравнения (1) является непрерывной функцией аргумента , то для отделения корней не обязательно строить график этой функции. В этом случае корни уравнения будут расположены между точками таблицы, где изменяется знак функции .
Шаг изменения аргумента при вычислении таблицы выбирается так, чтобы он был меньше расстояния между корнями. Только в этом случае удается отделить корни уравнения.
Программу, реализующую табличный метод отделения корней, составляется в соответствии с блок-схемой на рис.2. Блоки с нулевым номером входят в основную программу, а блок 1 представляет собой подпрограмму. В основной программе в диалоговом режиме задаем интервал , шаг изменения аргумента и параметры уравнения . Затем в цикле обращаемся к блоку 1, где осуществляется вычисление левой части уравнения, и выводим результаты в виде таблицы либо в виде графика.
Рис.2. Блок-схема программы табличного
метода решения уравнения (1)
П Р О Г Р А М М А П А С К А Л Ь
ДЛЯ ОТДЕЛЕНИЯ КОРНЯ УРАВНЕНИЯ ОДНОГО
НЕИЗВЕСТНОГО
program otdeleniya kornya;
var x,h,a,b,k:real;i,j:integer; label 1,2;
function f(x:real):real;
begin
f:=ln(x)+(x+1)*(x+1)*(x+1);
end;
function sgn(x:real):integer;
begin
sgn:=0;
if x<0.0 then sgn:=-1;
if x>0.0 then sgn:=1;
end;
begin
x:=0; h:=0.1;
1:
k:=f(x);
i:=sgn(k);
x:=x+h;
k:=f(x);
j:=sgn(k);
if i=j then goto 1 else goto 2;
2:
begin
a:=x-h;
b:=x;
end;
readln;
end.
6 Метод половинного деления отрезка для численного решения уравнения одного неизвестного
Пусть f Є C [a, b], f (a) · f (b) < 0 и известно, что уравнение f (x) = 0 имеет единственное решение (единственный корень) x* Є [a, b]. Полагаем а0 = а, b0 = b, c0 = (а0 + b0) / 2. Т.е. c0 – середина отрезка [а0, b0]. Вычисляем f (c0). Если f (c0) = 0, то х* = c0 и вычисления на этом заканчиваются. Если f (c0)≠ 0, то знак f (c0) совпадает со знаком f (а0), либо со знаком f (b0), так как
f (a0) · f (b0) < 0.
Таким образом, на концах одного из двух отрезков
[a0, b0] или [с0, b0] функция f имеет одинаковые знаки, а на концах другого – противоположные. Сохраняем отрезок, на концах которого f (x) имеет противоположные знаки, а другой отрезок, как не содержащий корень x*, отбрасываем. Остановленный отрезок обозначим через [ a1, b1], где
Очевидно, sign f (a1) = sign f (a0) и sign f (b1) = sign f (b0).
Поэтому f (a1) · f (b1) < 0
Искомый корень х* находится теперь на вдвое меньшем отрезке [ a1, b1]. Далее поступаем аналогично.
Допустим, что уже найден некоторый отрезок
[ aк , bк] < [ a, b], на концах которого функция f имеет противоположные знаки и следовательно, он содержит искомый корень х*. Находим середину отрезка [ aк , bк]:
ск = ak + bk / 2 (1)
Вычисляем f (ck). Если f (ck) = 0, то х* = ck , вычисления заканчиваются. Если f (ck) ≠ 0, то полагаем
и т.д.
Этот процесс может быть конечным, если середина отрезка, полученного на некотором шаге, совпадает с искомым корнем х*, либо этот процесс бесконечный.
Рис. 3
На рис.3 показано несколько начальных шагов. Если вычисления доведены до конечного шага, то в качестве приближенного значения для искомого корня х* естественно принять ск. При этом справедлива очевидная оценка погрешности
| x* - ck | ≤ (b – a) / 2k+1 (3)
Изложенный метод является типично машинным, так как
вычисления по формулам (1), (2) очень простые и цикличные. Он обладает достаточно быстрой сходимостью. На каждом шаге правая часть оценки погрешности (3) убывает вдвое.
П Р О Г Р А М М А П А С К А Л Ь
ДЛЯ ЧИСЛЕННОГО РЕШЕНИЯ УРАВНЕНИЯ ОДНОГО НЕИЗВЕСТНОГО МЕТОДОМ ПОЛОВИННОГО
ДЕЛЕНИЯ.
var P: ARRAY [1..9] of real;A,B,X,E:real;N,K:integer;
function f(x:real):real;
var R,R1,R2:real;
begin R:=1.0;R1:=sqrt(1.0-X);
while R-R1>P[2] do begin
R2:=(R+R1)/2; R1:=sqrt(R*R1);R:=R2
end;
F:=(R+R1)*P[1]-3.14159265
end;
function sgn(X:real):integer;
begin sgn:=0;
if x<0.0 then sgn:=-1;
if x>0.0 then sgn:=1
end;
procedure DICH(var A,B,X,E,E1:real); function f(x:real):real;
var I: integer; R:real;
begin i:=sgn(f(A));
while B-A>E do begin
X:=(A+B)/2; R:=f(x); if ABS(R)<E1 then exit;
if sgn(R)=I then A:=X else B:=X
end
end;
begin
repeat write('A,B,E? '); readln(A,B,E);
write('skolko parametrov? '); readln(N);
for K:=1 to N do begin
write('P(',K:2,')? '); readln(P[K])
end;
DICH (A,B,X,E,P[2]); writeln('X=',X);
until false
end;
7 Метод касательных и метод хорд для решения уравнения одного неизвестного.
Пусть нам требуется приближенно решить уравнения (1)
1. Если многочлен 5-ого и выше порядка, то решить это уравнение не представляется возможным. Для приближенного решения этого уравнения мы используем метод хорд или касательных. Для отыскания начального приближения к корню (изолированного) уравнения (1) необходимо отделить корни, т.е. найти отрезок , внутри которого имеется единственный корень.
Если:
(2)
то для отделения корня необходимо, чтобы выполнялись условия:
(3)
(на концах отрезка функция меняет знак)
или (4)
(функция монотонна внутри отрезка)
Для определения начальных концов отрезка, в которых могут выполняться условия (3), (4) можно воспользоваться равенством:
;
;
Если , то отрезок точкой
делится пополам и рассматривается
либо: либо: в зависимости от того, на концах какого из них выполняется (3).После этого также половинным делением добиваемся выполнения (4).
2. Пусть в уравнение (1) трансцендентная функция и требуется решить её приближённо. Для этого мы используем метод хорд или метод касательных.
Для отыскания начального приближения к корню уравнения необходимо, отделить корни, т.е. найти отрезок , внутри которого имеется единственный корень. Это можно делать или графически или используя производную функцию: найти области возрастания и убывания функций, и делением пополам сужать эти области, и найти отрезки, на концах которых будет выполняться условие:
или
(монотонность внутри отрезка)
Если мы нашли области возрастания и убывания, условие в этих областях можем не проверять. Для того чтобы отделить корни графически, перепишем в виде и построим график табличным или иным путём. Точки пересечения есть решение. Приближенно определим, в каком отрезке оно находится.
Метод касательных.
Рассмотрим уравнение
(1)
Предположим, что выше рассмотренными способами определен отрезок , внутри которого имеется единственный корень, т.е. выполняется условие
,
функция дважды дифференцируема и не
меняет знака на . Тогда возможны четыре случая,
изображенные на рис.4.
а) б)
в) г)
Рис.4
В методе касательных для выбора начального приближения необходимо проверить выполнение условия
где или .
Касательная к точке проводится со стороны выпуклости функции, там, где выполняется .
Предположим условие выполняется при , т.е.
,
Рис.5
Положим . Касательная, приходящая из точки , имеет уравнение:
(5)
которая пересекает ось в точке , .
Подставляя в (5), получим:
(6)
Это и есть первое приближение по методу касательных. Получаем отрезок, , в котором лежит решение.
Проверяем условие - точность.
Если выполняется, то , и дело прекращается, если это условие не выполняется, то точно также находим :
, …
Метод хорд.
В этом методе для выбора начального приближения необходимо проверить выполнение условия :
где или .
За начальное приближение выбирается тот из концов отрезка , для которого выполняется неравенство .
, или
Предположим условие выполняется при , т.е.
.
Рис.6
Положим .
Концы отрезка соединяются хордой и за следующие приближения принимаются значения абсцисс точки пересечения хорды с осью .
Напишем уравнение прямой, которая проходит через точки
и :
;
Абсцисса точки , являющая следующим приближением корня уравнения , может быть найдена из уравнения прямой, если положить в нём .
Тогда получим:
Для дальнейшего уточнения корня по способу хорд рассмотрим интервал и находим :
И так далее:
Комбинированный метод.
Суть этого метода заключается в том, что приближение для искомого значения корня уравнения:
вычисляется с двух сторон внутри .
С одной стороны, вычисления производятся по методу касательных, выбирая в качестве начального приближения точку, в которой выполняется неравенство , с другой – по методу хорд, выбирая в качестве точку, в которой выполняется
неравенство .
Этот метод применим, когда на сохраняет знак, т.е. при выполнении условия :
Начинаем вычисление по (6) и находим .
Пусть , тогда
;
По методу хорд находим :
Для -ого приближения получаем формулы:
, (7)
Слева - метод хорд, справа - метод касательных.
Или: и (8)
Слева - метод касательных, справа - метод хорд.
Получим вложенные отрезки:
Оценка погрешности может быть проведена по формуле:
Тогда:
где требуемая точность вычисления.
Вычислительная схема:
1) Отделение корня (определение ) методом половинного деления, т.е. проверка условия:
на концах различные знаки.
монотонность
2) Проверка условия:
Постоянство выпуклость или вогнутость.
3. Если условие n.2 выполняется, то проверяются условия , для выбора формул метода (либо (7) ), (либо (8)).
4. Вычисление очередных приближений по формулам (7) или (8).
5. Оценка точности: /
6) Если это условие не выполняется, повторяем вычисления по n.4.
Задание: Найти приближенное решение уравнения
(1)
комбинированным методом, с точностью .
Решение:
Отделим корень. Для определения начальных
концов отрезка , в котором могут выполнятся условия
и
т.е. на концах отрезка функция должна менять знак и
быть монотонной внутри , можно воспользоваться
равенствами:
Отсюда и из (1) находим
,
и .
Значить, решение находится в интервале .
Так как достаточно больше чем , мы попробуем
определить знак . Так как и , на
отрезке выполняется условие .
Проверим знак на .,
. Делим отрезок пополам:
.
Таким образом, внутри отрезка расположен один
изолированный корень. Вычислим
, Так как ,
сохраняет знак на и комбинированный метод
применим. Начинаем вычисления по методу касательной.
, значит, с точки применим метод
касательных, , значит с точки метод
хорд.
Положим .
По методу касательных находим
,
,
По методу хорд находим
, .
.
Вычислим и .
. .
Вычислим
Значить
П Р О Г Р А М М А П А С К А Л Ь
ДЛЯ РЕШЕНИЕ УРАВНЕНИЯ F(X)=0 НА ОТРЕЗКЕ [a,b] C ТОЧНОСТЬЮ ε ПРИ УСЛОВИИ, ЧТО ФУНКЦИЯ F(X) НА ОТРЕЗКЕ [a,b] МОНОТОННА И МЕНЯЕТ ЗНАК
uses crt;
var a,b,e,x:real;
function f(x:real):real;
begin
f:= ; (*Zdes zadayotsya vid funktsii*)
end;
function f1(x:real):real;
begin
f1:= ; (*Zdes zadayotsya vid 1-proizvodoy ot funktsii*)
end;
function f2(x:real):real;
begin
f2:= ; (*Zdes zadayotsya vid 2-proizvodnoy ot funktsii*)
end;
Procedure Prezentation;
begin
Clrscr;
Writeln ('Uchebnaya programma: ');
Writeln ('Resheniya uravneniya f(x)=0 na');
Writeln ('otrezke [a,b]s zadannoy tochnosti e');
Writeln ('pri uslovii chto funktsiya f(x)');
Writeln ('na otrezke [a,b] monotonna i') ;
Writeln ('menyaet znak') ;
Writeln ;Writeln;
end;
Procedure Input (var a,b,e:real);
begin
Write ('vvedite a='); Read(a);
Write('vvedite b='); Read(b);
Write('vvedite tochnost vichislennogo rezultata e=');
Read(e);
end;
Procedure Kombi(a,b,e:real;var x:real);
var c,d:real;
begin
While (b-a)>2*e do
begin
if f(a)*f2(a)<0
then begin c:=b-f(b)/f1(b); b:=c;
d:=a-(a-b)*f(a)/(f(a)-f(b)); a:=d;
end else begin c:=a-f(a)/f1(a); a:=c;
d:=b-(b-a)*f(b)/(f(b)-f(a));b:=d;
end; end;
x:=(a+b)/2;
Writeln (x:6:6);
end;
begin clrscr;
(*nachalo programmi*)
Prezentation;
Input (a,b,e);
Kombi (a,b,e,x);
Write ('Koren uravneniya x=',x:6:6);
end.
ТЕСТОВЫЕ ПРИМЕРЫ
f(x)=x-10*sinx=0
vvedite a=-0.5
vvedite b=0.5
vvedite tochnost vichislennogo rezultata e=0.0001
x=-0.024738
Koren uravneniya x=-0.024738
8 Метод итерации для численного решения нелинейных
уравнений и систем.
1. Решения нелинейных уравнений одного неизвестного.
Пусть дано уравнение с одной неизвестной х
х = , (1)
где - заданная функция от х.
Если не накладывать никаких ограничений на функцию , то могут возникнуть различные ситуации, а именно, уравнение (1) может иметь либо одно решение, либо некоторое конечное число решений (больше одного), либо бесконечное множество решений, либо, наконец, уравнение (1) может совсем не иметь решений. Обычно возникают сразу два вопроса: о наличии решений и о том, как найти решения. Мы формулируем теорему, которая дает достаточные условия существования на некотором отрезке единственного решения уравнения (1).
Эта теорема указывает также способ нахождения приближенного решения, называемой методом итераций, и обеспечивает оценки погрешности приближенного решения.
Определение. Говорят, что функция - удовлетворяет на отрезке [a, b] условию Липшица с постоянной α, если для любых х1, х2 Є [a, b] выполняется неравенство
| (x1) – (x2) | ≤ α |x1 – x2| (2)
Покажем пример класса функций, удовлетворяющая условию Липшица:
Пусть - функция непрерывна, дифференцируема на отрезке [a, b]. Тогда она удовлетворяет на [a, b] условию Липшица с постоянной
α max [a, b] | ’ (x) |, (3)
что легко следует из формулы Лагранжа.
Следующая теорема дает достаточные условия существования на некотором отрезке единственного решения уравнения (1) и указывает способ нахождения приближенного решения, называемый методом итераций, и обеспечивает оценки погрешности приближенного решения.{/spoilers}
