Приближенные численные методы

РЕШЕНИЕ НЕЛИНЕЙНОГО УРАВНЕНИЯ с одним неизвестным.

Уравнение с одним неизвестным можно записать в каноническом виде

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

Найти точные значения корней можно лишь в исключительных случаях. Как правило, используются методы приближенного вычисления корней с заданной степенью точности Е. Это означает, что если установлено, что искомый корень лежит внутри интервала , где a - левая граница, а b - правая граница интервала, и длина интервала (b-a) <= E, то за приближенное значение корня можно принять любое число, находящееся внутри этого интервала.

Процесс нахождения приближенных значений корней разбивается на два этапа: 1) отделение корней и 2) уточнение корней до заданной степени точности. Рассмотрим эти этапы подробнее.

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

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

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

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

При наличии компьютера наиболее распространен табличный способ отделения корней. Он заключается в табулировании функции f(x) при изменении х от некоторого значения х нач до значения х кон с шагом dx. Задача заключается в том, чтобы найти в этой таблице такие два смежных значения х, для которых функция имеет разные знаки. Предположим, что такие два значения a и b=a+dx найдены, т.е. f(a)*f(b)<0. Тогда согласно теореме Больцано-Коши внутри отрезка , если функция f(x) непрерывна, существует точка с, в которой f(c)=0. EXCEL позволяет легко реализовать оба способа отделения корней. Рассмотрим их на примере.

Пример 1.1.

Требуется отделить корни уравнения

Для этого надо протабулировать функцию f(Х) = exp(Х) - 10*Х, записанную по правилам EXCEL, и построить ее график при изменении Х от какого-то Х нач до Х кон с шагом dХ. Пусть эти значения сначала будут таковы: Х нач = 0, Х кон = 5, dХ = 0,5. Если в этих пределах изменения Х нам не удастся отделить ни одного корня, тогда надо будет задать новые начальное и конечное значения х и, может быть, изменить шаг.

Для построения таблицы целесообразно воспользоваться специальной подпрограммой ТАБЛИЦА. Для этого на новом рабочем листе в ячейке B1 введем текст: ОТДЕЛЕНИЕ КОРНЕЙ. Затем в ячейку А2 введем текст: x, а в смежную ей ячейку В2 - текст: f(x). Далее оставим ячейку А3 пустой, но в ячейку В3 введем формулу исследуемой функции по правилам EXCEL, а именно

Затем заполним числовой ряд изменений X в строках А4:A14 от 0 до 5 с шагом 0,5.

Выделим блок ячеек А3:B14. Теперь дадим команду меню Данные- Таблица . Результаты табулирования будут помещены в блок ячеек В4:В14. Для того чтобы сделать их более наглядными, нужно отформатировать блок В4:B14 так, чтобы отрицательные числа окрашивались в красный цвет. В этом случае легко найти два смежных значения X, для которых значения функции имеют разные знаки. Их и надо принять за концы интервала отделения корней. В нашем случае таких интервалов, как видно из таблицы два - и [ 3,5;4].

Далее следует построить график нашей функции, выделив блок А4:B14 и вызвав Мастер Диаграмм . В результате получим на экране диаграмму изменения f(X), из которой видны следующие интервалы отделения корней и .

Если изменять теперь числовые значения х в блоке А4:A14 то значения функции в ячейках B4:B14и график будут изменяться автоматически.

1.2 Уточнение корней: метод итераций.

Для уточнения корня методом итераций должно быть задано:

Сам метод можно разбить на два этапа:
а) переход от канонического вида записи уравнения f(X)=0 к итерирующему виду X = g(X),
б) вычислительная итерирующая процедура уточнения корня.

Перейти от канонического вида уравнения к итерирующему можно различными способами, важно лишь чтобы при этом выполнялось достаточное условие сходимости метода: çg’(X)ç<1 на , т.е. модуль первой производной итерирующей функции должен быть меньше 1 на интервале . Причем чем меньше этот модуль, тем больше скорость сходимости.

Вычислительная процедура метода состоит в следующем. Выбираем начальное приближение, обычно равное Х 0 = (a+b)/2. Затем вычислим X 1 =g(X 0) и D= X 1 - X 0 . Если модуль D <= E, то X 1 является корнем уравнения. В противном случае переходим ко второй итерации: вычисляем Х 2 =g(X 1) и новое значение D=X 2 - X 1 . Опять проводим проверку на точность и при необходимости продолжаем итерации. Если g(X) выбрано правильно и удовлетворяет достаточному условию сходимости, то эта итерирующая процедура сойдется к корню. Следует отметить, что от знака g’(X) зависит характер сходимости: при g’(X)>0 сходимость будет монотонной , т.е. с увеличением итераций D будет приближаться к Е монотонно (не меняя знака), в то время как при g’(X)<0 сходимость будет колебательной , т.е. D будет приближаться к Е по модулю, меняя знак на каждой итерации.

Рассмотрим реализацию метода итераций на EXCEL на примере.

Пример 1.2

Уточним методом итераций значение корней, отделенных в примере 2.1. Итак пусть f(X)= exp(X) - 10*X, для первого корня a=0 и b=0,5. Пусть Е=0,00001. Как выбрать итерирующую функцию? Например, так g(X)=0,1*exp(X). На интервале çg’(X)ç<1 и достаточное условие сходимости выполняется. Кроме того, эта производная >1 на интервале и характер сходимости будет монотонный.

Запрограммируем метод итераций для этого примера на том же рабочем листе, где мы проводили отделение корней. В ячейку А22 внесем число, равное 0. В ячейку В22 запишем формулу =0,1*EXP(A22), а в ячейку С22 формулу =А22- В22. Таким образом 22 строка содержит данные по первой итерации. Чтобы получить в строке 23 данные по второй итерации, скопируем содержимое ячейки В22 в ячейку А23, записав в А23 формулу =В22. Далее надо скопировать формулы ячеек В22 и С22 в ячейки В23 и С23. Для получения данных всех остальных итераций надо выделить ячейки А23,В23,С23 и скопировать их содержимое в блок А24:C32. После этого следует проанализировать изменение D = Х - g(X) в столбце С, найти D<0,00001 по модулю и выбрать соответствующее ему значение Х из столбца А. Это и есть приближенное значение корня.

Для большей наглядности можно построить диаграмму для метода итераций. Выделяя блок А22:С32 и используя Мастер диаграмм , получим три графика изменения Х,g(X) и D в зависимости от номера итераций, для чего на шаге 3 из 5 выберем формат 2, а на шаге 4 из 5 построения диаграммы нужно отвести ноль столбцов для меток оси Х. Теперь хорошо виден монотонный характер сходимости D.

Для уточнения второго корня этого уравнения на интервале , нужно выбрать другую итерирующую функцию, такую чтобы ее первая производная была по модулю меньше единицы. Выберем g(X)= LN(X)+LN(10). В ячейку А22 внесем новое Х0=3,75, а в ячейку В22 - новую формулу =LN(A22)+LN(10). Скопируем формулу из В22 в блок В23:В32 и сразу получим новые данные и перестроенную диаграмму. Определим приближенное значение второго корня.

1.3 Уточнение корней: метод Ньютона.

Для уточнения корня методом Ньютона должно быть дано:

1) уравнение f(X) = 0, причем f(X) должно быть задано в виде формулы,

2) числа a - левая граница и b - правая граница интервала, внутри которого лежит один корень,

3) число Е - заданная точность получения корня,

4) функция f(X) должна быть дважды дифференцируемой, причем формулы f’(X) и f”(X) должны быть известны.

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

X i+1 = X i - f(X i)/f’(X i), где i=0,1,2, ...,

исходя из начального приближения Х 0 , принадлежащего интервалу и удовлетворяющего условию f(X 0)*f”(X 0)>0. Достаточные условия сходимости метода заключаются в том, что первая и вторая производные исследуемой функции должны сохранять знак на интервале . В качестве начального приближения выбирают обычно или a, или b, в зависимости от того, кто из них соответствует формуле выбора Х 0 .

Метод Ньютона допускает простую геометрическую интерпретацию. Если через точку с координатами (X i ;f(X i)) провести касательную к кривой f(X), то абсцисса точки пересечения этой касательной с осью 0Х и есть очередное приближение корня Х i+1 .

Метод Ньютона можно рассматривать как некоторую модификацию метода итераций, дающую наилучшую итерирующую функцию g(X) на каждом шаге итерации. Проведем следующие преобразования с исходным каноническим уравнением f(X)=0. Умножим левую и правую его части на некоторое число l, отличное от нуля. Затем прибавим слева и справа по Х. Тогда будем иметь

Х = g(X) = Х +l*f(X).

Дифференцируя g(X), получим g’(X) = 1 + l*f’(X). Из достаточного условия сходимости метода итераций çg’(X)ç<1. Потребуем, чтобы на i-том шаге итерации сходимость была самой быстрой, т.е. çg’(X i)ç =0. Тогда l=-1/ f’(X i) и мы пришли к методу Ньютона.

Вычислительная процедура метода состоит в следующем. Выбираем начальное приближение X 0 , обычно равное a или b. Затем вычислим X 1 = X 0 - f(X 0)/f’(X 0) и D= X 1 - X 0 . Если модуль D <= E, то X 1 является корнем уравнения. В противном случае переходим ко второй итерации: вычисляем Х 2 и новое значение D=X 2 - X 1 . Опять проводим проверку на точность и при необходимости продолжаем итерации. Если X 0 выбрано правильно, а функция удовлетворяет достаточному условию сходимости, то эта итерирующая процедура быстро сойдется к корню.

Пример 1.3.

Уточним методом Ньютона значение корня, отделенного в примере 1.1. Итак пусть f(X)= exp(X) - 10*X, для первого корня a=0 и b=0,5. Пусть Е=0,00001. Формулы для первой и второй производной f(X) таковы

f’(X) = exp(X) - 10 и f”(X) = exp(X).

Очевидно, что X 0 = a = 0, т.к. f(0)*f”(0) = 1 >0.

Чтобы получить в строке 43 данные по второй итерации, скопируем содержимое ячейки D42 в ячейку А43, записав в А43 формулу =D42. Далее надо скопировать формулы ячеек В42, С42, D42, E42 в ячейки В43, С43, D43, E43. Для получения данных всех остальных итераций надо выделить ячейки в 43 строке и скопировать их содержимое в блок А44:Е47. После этого следует проанализировать изменение D в столбце E, найти D<0,00001 по модулю и выбрать соответствующее ему значение Х из столбца А. Это и есть приближенное значение корня. При правильно введенных формулах метод Ньютона сходится за 3 или 4 итерации. Поэтому строить диаграмму для этого метода нет необходимости.

1.4. Уточнение корней: метод бисекции (деления отрезка пополам).

Для уточнения корня методом бисекции должно быть дано:

1) уравнение f(X) = 0, причем f(X) должна быть задана в виде формулы,

2) числа a - левая граница и b - правая граница интервала, внутри которого лежит один корень,

3) число Е - заданная точность получения корня.

Напомним, что на концах интервала функция f(X) имеет разные знаки. Вычислительная процедура метода состоит в том, что на каждом шаге итерации на интервале выбирают промежуточную точку с так, чтобы она являлясь серединой интервала, т.ет с=(a+b)/2. Тогда интервал разделится этой точкой на два равных отрезка и , длины которых равны (b-a)/2. Из двух полученных отрезков выберем тот, на концах которого функция f(X) принимает значения противоположных знаков. Обозначим его снова как . На этом заканчивается первая итерация. Далее новый отрезок делим снова пополам и проводим вторую и последующие итерации. Процесс деления отрезка пополам производим до тех пор, пока на каком-либо К-том шаге вновь получающийся отрезок не станет меньше или равным величине точности Е. Значение шага К легко рассчитать из формулы

(b-a)/2 k <=E,

где a и b - начальные значения левой и правой границ интервала.

Метод бисекций сходится для любых непрерывных функций, в том числе и недифференцируемых.

Пример 1.4.

Уточним методом бисекции значение корня, отделенного в примере 1.1. Итак пусть f(X)= exp(X) - 10*X, для первого корня a=0 и b=0,5. Пусть Е=0,00001.

Запрограммируем метод бисекции для этого примера на том же рабочем листе, где мы проводили отделение корней. В ячейки А52 и В52 надо внести числовые значения a и b,в ячейку С52 - формулу =(А52+В52)/2. Далее в ячейку D52 внесем формулу =EXP(A52)-10*A52, в ячейку Е52 - формулу =EXP(C52)-10*C52, в ячейку F52 - формулу =D52*E52, и, наконец, в ячейку G52 запишем формулу =B52- A52. В строке 52 мы сформировали первую итерацию. На второй итерации значения в ячейках А53 и В53 зависят от знака числа в ячейке F52. Если F52>0, то значение А53 равно С52. В противном случае оно должно быть равно А52. В ячейке В53 наоборот: если F52<0, то значение В53 равно С52, иначе В52.

Разрешить это затруднение поможет встроенная функция EXCEL, которая носит название ЕСЛИ. Сделаем текущей ячейку А53. В строке формул, рядом с зеленой галочкой щелкнем на кнопке с изображением f(x) . Так вызывается Мастер Функций . В появившемся диалоге выберем в поле Категории Функции категорию Логические , а в поле Имя Функции - имя ЕСЛИ. На втором шаге диалога заполним три свободных поля следующим образом: в поле Логическое_выражение внесем “F52>0” (разумеется без кавычек!), в поле Значение_если_истина внесем С52, а в поле Значение_если_ложь - А52. Щелкнем по кнопке Закончить . Вот и все.

То же самое надо проделать с ячейкой В53. Только Логическое выражение будет “F52<0”, Значение_если_истина будет С52, а Значение_если_ложь соответственно В52.

Далее надо скопировать формулы в блоке ячеек С52:G52 в блок С53:G53. После этого вторая итерация будет проведена в строке 53. Для получения следующих итераций достаточно скопировать формулы из строки 53 в блоке А53:E53 в блок А54: E68. Затем, как обычно, следует найти с столбце Е такую строку, где значение D будет меньше Е. Тогда число в столбце С в этой строке и есть приближенное значение корня.

Можно построить диаграмму изменения значений в столбцах А, В и С, начиная с первой и кончая последней итерацией. Для этого нужно выделить блок ячеек А52:С68. За дальнейшими инструкциями обратитесь к примеру 1.2.

Уточним значение корня, отделенного в примере 1.1. Итак пусть f(X)= exp(X) - 10*X. Найдем корень, лежащий на интервале . Оставим пустой ячейку А70. В ячейку В70 запишем формулу =EXP(A70)-10*A70. Выберем команду меню Сервис - Подбор параметра . Откроется диалог Подбор параметра , в котором в поле Установить в ячейке запишем В70, в поле Значение занесем 0 (ноль), в поле Изменяя ячейку укажем А70. Щелкнем по кнопке ОК и появится новый диалог, в котором будет показан результат выполнения операции. В окне Состояние подбора решения будет показано найденное значение. Теперь если щелкнуть на кнопке ОК, в ячейку А70 будет внесено найденное значение корня, а в ячейку B70 - значение функции.

Для того, чтобы найти другой корень, лежащий на интервале необходимо изменить начальное приближение, которое в нашей таблице находится в ячейке A70. Запишем в эту ячейку одну из границ интервала, например, 4, и снова выполним процедуру подбора параметра. Содержимое клеток A70 и B70 изменится, теперь в этих клетках появятся координаты большего корня.

2. СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

В общем виде система линейных алгебраических уравнений записывается так: a 11 x 1 +a 12 x 2 +... +a 1n x n = b 1

a 21 x 1 +a 22 x 2 +... +a 2n x n = b 2

......................

a n1 x n +a n2 x 2 +... +a nn x n = b n

Совокупность коэффициентов этой системы запишем в виде квадратной матрицы A из n строк и n столбцов

a 11 a 12 ... a 1n

a 21 a 22 ... a 2n

a n1 a n2 ... a nn

Используя матричное исчисление, исходную систему уравнений можно записать в виде

А*Х = В,

где Х - вектор- столбец неизвестных размерностью n , аВ - вектор- столбец свободных членов, тоже размерностью n .

Эта система называется совместной , если она имеет хотя бы одно решение, и определенной , если она имеет одно единственное решение. Если все свободные члены равны нулю, то система носит название однородной .

Необходимым и достаточным условием существования единственного решения системы является условие DET=0, где DET - определитель матрицы А . На практике при вычислениях на компьютере не всегда удается получить точное равенство DET нулю. В том случае, когда DET близко к нулю, системы называются плохо обусловленными. При их решении на компьютере малые погрешности в исходных данных могут привести к существенным погрешностям в решении. Условие DET~0 является необходимым для плохой обусловленности системы, но не достаточным. Поэтому при решении системы на ЭВМ требуется оценка погрешности, связанной с ограниченностью разрядной сетки компьютера.

Существуют две величины, характеризующие степень отклонения полученного решения от точного. Пусть Хк - истинное решение системы, Хc - решение, полученное тем или иным методом на ЭВМ, тогда погрешность решения:
Е = Хк - Хc . Вторая величина - невязка, равная R = B - A*Xc . В практических расчетах контроль точности осуществляется с помощью невязки, хотя это и не совсем корректно.

2.1. Матричный метод.

EXCEL дает возможность решить систему линейных алгебраических уравнений матричным методом, т.е.

Х = А -1 *В.

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

1) получить матрицу А -1 , обратную матрицеА ;

2) получить решение системы по формуле Хс = А -1 *В;

3) вычислить новый вектор свободных членов Вс = А*Хс ;

4) вычислить невязку R = B - Bc ;

5) получить решение системы по формулеdXc = А -1 *R ;

6) сравнить все компоненты вектора dXc по модулю с заданной погрешностью Е: если все они меньше Е, то закончить вычисления, иначе повторить вычисления с п.2, гдеХс = Xc + dXc .

Рассмотрим матричный метод решения системы с помощью EXCEL на примере.

Пример 2.1.

Решить систему уравнений

20,9x 1 + 1,2x 2 + 2,1x 3 + 0,9x 4 = 21,7

1,2x 1 +21,2x 2 + 1,5x 3 + 2,5x 4 = 27,46

2,1x 1 + 1,5x 2 +19,8x 3 + 1,3x 4 = 28,76

0,9x 1 + 2,5x 2 + 1,3x 3 +32,1x 4 = 49,72

EXCEL имеет следующие встроенные функции, реализующие матричные вычисления:

а) МОБР - обращение матрицы,

б) МУМНОЖ - умножение двух матриц,

в) МОПРЕД - вычисление определителя матрицы.

При использовании этих функций важно правильно и компактно расположить на рабочем листе блоки ячеек, соответствующие исходным и рабочим матрицам и вектор-столбцам. Откроем новый рабочий лист, щелкнув на выбранном Вами ярлычке. Отведем под матрицу А блок ячеек А3:D6. Для наглядности заключим его в черную рамку. Для этого выделим блок A3:D6, дадим команду меню Формат- Ячейки и в открывшемся диалоге выберем вкладку Рамка . Откроется новый диалог, в котором щелкнем по полю Рамка- Контур и выберем в поле Рамка- Стиль самую толстую ширину линии. Подтвердим свое решение, щелкнув на кнопке ОК. Выделим теперь блок A8:D11 под матрицу А -1 и также заключим его в черную рамку, проделав действия, аналогичные блоку матрицы А . Далее выделим блоки ячеек под вектор-столбцы (обведя их черной рамкой): блок F8:F11 - под векторВ , блок H8:H11 - под вектор Хс А -1 *В , блок H3:H6 - под вектор Вс , получающийся в результате умноженияА*Хс , причем для наглядности выделим дополнительный блок F3:F6, куда скопируем компоненты вектора Хс из блока H8:H11. И наконец, занесем в ячейки Е4 и Е9 знак умножения *, а в ячейки G4 и G9 знак равенства =, затем, выделяя по очереди столбцы Е и G, дадим команду меню Формат- Столбец - Подгон ширины . Таким образом мы подготовили рабочий лист к решению нашей задачи.

Внесем исходные данные: числа матрицы А в ячейки блока A3:D6, а числа вектора свободных членовВ - в ячейки блока F8:F11.

Начнем выполнение алгоритма с обращения матрицы А . Для этого выделим блок А8:D11, куда должен быть помещен результат операции. Этот блок окрасится в черный цвет, за исключением ячейки А8. Щелкнем по кнопке f x на панели Стандартная , осуществив вызов Мастера Функций . Откроется диалог, в котором из поля Категория функций выберем строку Мат. и тригонометрия , а из поля Имя функции - строку МОБР. Перейдем ко второму шагу диалога, щелкнув по кнопке Шаг> . Здесь в поле Массив надо набить с клавиатуры А3:D6, что соответствует блоку ячеек, занятому матрицей А . Щелкнув на кнопке Закончить , можно увидеть, что в блоке А8:D11 заполнена лишь ячейка А8. Для завершения операции обращения EXCEL требует выполнения еще двух действий. Сначала надо сделать активной строку формул, щелкнув по ней (в любом месте строки!) - курсор мыши примет при этом форму I. Проверкой правильности Ваших действий будет появление слева от строки формул четырех кнопок, в том числе с зеленой галочкой. После этого следует нажать на клавиатуре клавишу “Ctrl”, затем не отпуская ее - клавишу “Shift”, и не отпуская и ее - клавишу “Enter”, т.е. в результате должны быть нажаты все три клавиши одновременно! Вот теперь весь блок А8:D11 будет заполнен числами и можно выделить блок H8:H11, чтобы начать операцию умножения А -1 *В .

Выделив этот блок, снова вызовите Мастер функций и в поле Имя функции - выбирайте функцию МУМНОЖ. Щелкнув по кнопке Шаг> , перейдем ко второму шагу диалога, где в поле Массив1 внесем адрес А8:D11, а в поле Массив2 - адрес F8:F11. Щелкнем по кнопке Закончить и обнаружим, что в блоке Н8:H11 заполнена лишь ячейка Н8. Активизируем строку формул (должна появиться зеленая галочка!) и по методике, описанной выше, нажмем одновременно три клавиши “Ctrl”-”Shift”-”Enter”. Результат умножения появится в блоке Н8:H11.

Для проверки точности полученного решения системы, проведем операцию вычисленияВс=А*Хс . С этой целью скопируем только числовые значения (а не формулы!) ячеек из блока H8:H11 в ячейки F3:F6. Сделать это надо следующим образом. Выделим блок H8:H11. Дадим команду меню Правка - Копировать . Выделим блок F3:F6. Дадим команду меню Правка - Специальная вставка . Откроется диалог, в котором в поле Вставить следует выбрать режим Значения . Подтвердим свое решение, щелкнув по кнопке ОК.

После этой операции заполнены числами блоки А3:D6 и F3:F6. Можно приступить к умножению матрицы А на вектор Хс . Для этого надо выделить блок Н3:H6, вызвать Мастер Функций и, действуя так же, как и при вычислении Хс=А -1 *В , получить Вс . Как видно из таблицы, числовые значения векторов В и Вс совпадают, что говорит о хорошей точности вычислений, т.е. невязка в нашем примере равна нулю.

Подтвердим хорошую обусловленность матрицы А вычислением ее определителя. Для этого сделаем активной ячейку D13. С помощью Мастера Функций вызовем функцию МОПРЕД. В поле массив занесем адрес блока А3:D6. Щелкнув по кнопке Закончить , получим в ячейке D13 числовое значение определителя матрицы А . Как видно, оно значительно больше нуля, что говорит о хорошей обусловленности матрицы.

2.2. Метод приближенных вычислений.

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

Пусть надо решить систему

a 11 x 1 +a 12 x 2 +a 13 x 3 = b 1

a 21 x 1 +a 22 x 2 +a 23 x 3 = b 2

a 31 x 1 +a 32 x 2 +a 33 x 3 = b 3

Предположим, что диагональные элементы a 11, a 22, a 33 отличны от нуля. В противном случае можно переставить уравнения. Выразим переменные из первого, второго и третьего уравнений соответственно. Тогда

x 1 = / a 11

x 2 = / a 22

x 3 = / a 33

Зададим начальные приближения неизвестных

Подставляя их в правую часть преобразованной системы, получим новое первое приближение

Нахождение корней уравнений

Графический способ нахождения корней заключается в построении графика функции f(x) на отрезке . Точка пересечения графика функции с осью абсцисс дает приближенное значение корня уравнения.

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

При нахождении корней расчетным путем для непрерывных функций f(x) руководствуются следующими соображениями:

– если на концах отрезка функция имеет разные знаки, то между точками a и b на оси абсцисс имеется нечетное число корней;

– если же функция имеет одинаковые знаки на концах интервала, то между a и b имеется четное число корней или их совсем нет;

– если на концах отрезка функция имеет разные знаки и либо первая производная, либо вторая производная не меняют знаки на этом отрезке, то уравнение имеет единственный корень на отрезке .

Найдем все действительные корни уравнения x 5 –4x–2=0 на отрезке [–2,2]. Создадим электронную таблицу.

Таблица 1

В таблице 2 получены результаты расчета.

Таблица 2

Аналогично находится решение на интервалах [-2,-1], [-1,0].

Уточнение корней уравнения

С использованием режима «Поиск решений»

Для данного выше уравнения следует уточнить с погрешностью Е=0,001 все корни уравнения x 5 –4x–2=0.

Для уточнения корней на интервале [-2,-1] составим электронную таблицу.

Таблица 3

Запускаем режим «Поиск решения» в меню «Сервис». Выполняем команды режима. Режим показа отобразит найденные корни. Аналогично уточняем корни на других интервалах.

Уточнение корней уравнений

С использованием режима «Итерации»

Метод простых итераций имеет два режима «Вручную» и «Автоматически». Для запуска режима «Итерации» в меню «Сервис» открывают вкладку «Параметры». Далее следуют командам режима. На вкладке «Вычисления» можно выбрать режим автоматический или ручной.

Решение систем уравнений

Решение систем уравнений в Excel проводится методом обратных матриц. Решить систему уравнений:

Создадим электронную таблицу.

Таблица 4

	A	B	C	D	E
	Решение системы уравнений.
		Ax=b
	Исходная матрица А		Правая часть b
	-8
			-3
			-2		-2
	Обратная матрица (1/А)		Вектор решения x=(1/A)/b
	=МОБР(А6:С8)	=МОБР(А6:С8)	=МОБР(А6:С8)		=МУМНОЖ(А11:С13;Е6:Е8)
	=МОБР(А6:С8)	=МОБР(А6:С8)	=МОБР(А6:С8)		=МУМНОЖ(А11:С13;Е6:Е8)
	=МОБР(А6:С8)	=МОБР(А6:С8)	=МОБР(А6:С8)		=МУМНОЖ(А11:С13;Е6:Е8)

Функция МОБР возвращает массив значений, который вставляется сразу в целый столбец ячеек.

В таблице 5 представлены результаты расчета.

Таблица 5

	A	B	C	D	E
	Решение системы уравнений.
		Ax=b
	Исходная матрица А		Правая часть b
	-8
			-3
			-2		-2
	Обратная матрица (1/А)		Вектор решения x=(1/A)/b
	-0,149	0,054	-0,230
	0,054	0,162	-0,189
	-0,122	0,135	-0,824

Список использованных литературных источников

1. Турчак Л.И. Основы численных методов: Учеб. пособие для вузов/ ред. В.В. Щенников.–М.: Наука, 1987.–320с.

2. Банди Б. Методы оптимизации. Вводный курс.–М.: Радио и связь, 1988.–128с.

3. Евсеев А.М., Николаева Л.С. Математическое моделирование химических равновесий.–М.: Изд-во Моск. ун-та, 1988.–192с.

4. Безденежных А.А. Инженерные методы составления уравнений скоростей реакций и расчета кинетических констант.–Л.: Химия, 1973.–256с.

5. Степанова Н.Ф., Ерлыкина М.Е., Филиппов Г.Г. Методы линейной алгебры в физической химии.–М.: Изд-во Моск. ун-та, 1976.–359с.

6. Бахвалов Н.С. и др. Численные методы в задачах и упражнениях: Учеб. пособие для вузов/ Бахвалов Н.С., Лапин А.В., Чижонков Е.В. - М.: Высш. шк., 2000.-190с. - (Высшая математика/ Садовничий В.А.)

7. Применение вычислительной математики в химической и физической кинетике, под ред. Л.С. Полак, М.: Наука, 1969, 279 стр.

8. Алгоритмизация расчетов в химической технологии Б.А. Жидков, А.Г. Бондарь

9. Вычислительные методы для инженеров-химиков. Х.Розенброк, С.Стори

10. Орвис В.Д. Excel для ученых, инженеров и студентов. – Киев: Юниор, 1999.

11. Ю.Ю. Тарасевич Численные методы на Mathcade – Астраханский гос.пед.ун-т: Астрахань, 2000.

Министерство общего образования

Российской федерации

Уральский государственный технический университет-УПИ

филиал в г.Краснотурьинске

Кафедра вычислительной техники

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

По численным методам

Решение линейных уравнений методом простой итерации

c помощью программы Microsoft Excel

Руководитель Кузьмина Н.В.

Студент Нигматзянов Т.Р.

Группа М-177Т

Тема: «Нахождение с заданной точностью корня уравнения F(x)=0 на промежутке методом простой итерации».

Контрольный пример: 0,25-х+sinx=0

Условия задачи: для заданной функции F(x) на интервале найти корень уравнения F(x)=0 методом простой итерации.

Корень вычислить дважды(с помощью автоматического и ручного расчета).

Предусмотреть построение графика функции на заданном интервале.

Введение 4

1.Теоретическая часть 5

2.Описание хода работы 7

3.Входные и выходные данные 8

Заключение 9

Приложение 10

Библиографический список 12

Введение.

В ходе данной работы мне необходимо ознакомиться с различными методами решения уравнения и найти корень нелинейного уравнения 0,25-х+sin(x)=0 численным методом – методом простой итерации. Для проверки правильности нахождения корня необходимо решить уравнение графически,найти приближенное значение и сравнить его с полученным результатом.

1.Теоретичесакя часть.

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

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

Для использования этого метода исходное нелинейное уравнение записывается в виде: х=j(х), т.е. выделяется х; j(х) – непрерывна и дифференцируема на интервале (а; в). Обычно это можно сделать несколькими способами:

Например:

arcsin(2x+1)-x 2 =0 (f(x)=0)

Способ 1.

arcsin(2x+1)=x 2

sin(arcsin(2x+1))=sin(x 2)

x=0.5(sinx 2 -1) (x=j(x))

Способ 2.

x=x+arcsin(2x+1)-x 2 (x=j(x))

Способ 3.

x 2 =arcsin(2x+1)

x= (x=j(x)),знак берется в зависимости от интервала [а;b].

Преобразование должно быть таким, чтобы ½j(x)<1½ для всех принадлежащих интервалу .В таком случае процесс итерации сходится.

Пусть известно начальное приближение корня x=c 0 .Подставляя это значение в правую часть уравнения x=j(x),получаем новое приближение корня:c=j(c 0).Далее, подставляя каждый раз новое значение корня в x=j(x),получаем последовательность значений

c n =j(c n-1) n=1,2,3,…

Процесс итераций следует продолжать до тех пор,пока для двух последовательных приближений не будет выполнено условие: ½c n -c n -1 ½

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

Программа Excel реализует метод простой итерации двумя способами с помощью ручного расчета и с автоматическим контролем точности.

у у=х

j(с 0)

с 0 с 2 с 4 с 6 с 8 корень с 9 с 7 с 5 с 3 с 1

	Рис. График итерационного процесса

2.Описание хода работы.

1. Запустил МЕ.

2. Построил график функции y=x и y=0,25+sin(x) на отрезке с шагом 0,1 назвал лист «График».

3. Выбрал команду Сервис ® Параметры.
Открыл вкладку Вычисления .
Включил режим Вручную .
Отключил флажок Пересчет перед сохранением . Сделал значение поля Пре-дельное число итераций равным 1,относительную погрешность 0,001.

4. Ввел в ячейку А1 строку «Решение уравнения x=0,25+sin(x) методом простой итерации».

5. Ввел в ячейку А3 текст «Начальное значение»,в ячейку А4 текст «Начальный флаг»,в ячейку В3 значение 0,5 ,в ячейку В4 слово ИСТИНА.

6. Присвоил ячейкам В3 и В4 имя «нач_зн» и «нач».
В ячейке В6 будет выполняться проверка,равна ли истина значению ячейки «нач».Если это так,х будет установлено равным начальному значению, в противоположном случае равным ячейке В7,т.е. 0,25+синуса х.В ячейке В7 выч-исляется 0,25-синуса ячейки В6,и тем организуется циклическая ссылка.

7. В ячейку А6 ввел y=x,и в ячейку А7 y=0,25+sin(x).В ячейку В6 формулу:
=ЕСЛИ(нач;нач_зн;В7).
В ячейку В7 формулу: y=0,25+sin(B6).

8. В ячейку А9 ввел слово Погрешность.

9. В ячейку В9 ввел формулу: =В7-В6.

10. С помощью команды Формат-Ячейки (вкладка Число ) преобразовал ячейку В9 в экспоненциальный формат с двумя цифрами после запятой.

11. Затем организовал вторую циклическую ссылку-для подсчета количества ите-раций.В ячейку А11 ввел текст «Количество итераций».

12. В ячейку В11 ввел формулу: =ЕСЛИ(нач;0;В12+1).

13. В ячейку В12 ввел =В11.

14. Для выполнения расчета установил табличный курсор в ячейку В4 и нажал клавишу F9(Вычислить) для запуска решения задачи.

15. Изменил значение начального флага на ЛОЖЬ,и снова нажал F9.При каждом нажатии F9 выполняется одна итерация и вычисляется следующее приближен-ное значение х.

16. Нажимал клавишу F9 до тех пор, пока значение х не достигло необходимой точности.
При автоматическом расчете:

17. Перешел на другой лист.

18. Повторил пункты с 4 по 7,только в ячейку В4 ввел значение ЛОЖЬ.

19. Выбрал команду Сервис ® Параметры (вкладка Вычисления ).Установил зна-чение поля Предельное число итераций равным 100,относительную погреш-ность равной 0,0000001.Включил ркжим Автоматически .

3.Входные и выходные данные.

Начальный флаг ЛОЖЬ.
Начальное значение 0,5

Функция y=0,25-x+sin(x)

Границы интервала

Точность вычисления при ручном расчете 0,001

при автоматическом

Выходные:

1. Ручной расчет:
число итераций 37
корень уравнения 1,17123

2. Автоматический расчет:
число итераций 100
корень уравнения 1,17123

3. Решение уравнения графическим способом:
корень уравнения 1,17

Заключение.

В ходе данной курсовой работы я ознакомился с различными методами решения уравнений:

· Аналитическим методом

· Графическим методом

· Численным методом

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

Нашел с заданной точностью корень уравнения 0,25-x+sin(x)=0 на промежутке методом простой итерации.

Приложение.

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

2.Автоматический расчет.

3.Решение уравнения 0.25-x-sin(x)=0 графическим способом.

Библиографический список.

1. Волков Е.А. «Числовые методы».

2. Самарский А.А. «Введение в числовые методы».

3. Игалеткин И.И. «Числовые методы».

В программе Excel имеется обширный инструментарий для решения различных видов уравнений разными методами.

Рассмотрим на примерах некоторые варианты решений.

Решение уравнений методом подбора параметров Excel

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

Путь к команде: «Данные» - «Работа с данными» - «Анализ «что-если»» - «Подбор параметра».

Рассмотрим на примере решение квадратного уравнения х 2 + 3х + 2 = 0. Порядок нахождения корня средствами Excel:

Для подбора параметра программа использует циклический процесс. Чтобы изменить число итераций и погрешность, нужно зайти в параметры Excel. На вкладке «Формулы» установить предельное количество итераций, относительную погрешность. Поставить галочку «включить итеративные вычисления».



Как решить систему уравнений матричным методом в Excel

Дана система уравнений:

Получены корни уравнений.

Решение системы уравнений методом Крамера в Excel

Возьмем систему уравнений из предыдущего примера:

Для их решения методом Крамера вычислим определители матриц, полученных заменой одного столбца в матрице А на столбец-матрицу В.

Для расчета определителей используем функцию МОПРЕД. Аргумент – диапазон с соответствующей матрицей.

Рассчитаем также определитель матрицы А (массив – диапазон матрицы А).

Определитель системы больше 0 – решение можно найти по формуле Крамера (D x / |A|).

Для расчета Х 1: =U2/$U$1, где U2 – D1. Для расчета Х 2: =U3/$U$1. И т.д. Получим корни уравнений:

Решение систем уравнений методом Гаусса в Excel

Для примера возьмем простейшую систему уравнений:

3а + 2в – 5с = -1
2а – в – 3с = 13
а + 2в – с = 9

Коэффициенты запишем в матрицу А. Свободные члены – в матрицу В.

Для наглядности свободные члены выделим заливкой. Если в первой ячейке матрицы А оказался 0, нужно поменять местами строки, чтобы здесь оказалось отличное от 0 значение.

Примеры решения уравнений методом итераций в Excel

Вычисления в книге должны быть настроены следующим образом:

Делается это на вкладке «Формулы» в «Параметрах Excel». Найдем корень уравнения х – х 3 + 1 = 0 (а = 1, b = 2) методом итерации с применением циклических ссылок. Формула:

Х n+1 = X n – F (X n) / M, n = 0, 1, 2, … .

M – максимальное значение производной по модулю. Чтобы найти М, произведем вычисления:

f’ (1) = -2 * f’ (2) = -11.

Полученное значение меньше 0. Поэтому функция будет с противоположным знаком: f (х) = -х + х 3 – 1. М = 11.

В ячейку А3 введем значение: а = 1. Точность – три знака после запятой. Для расчета текущего значения х в соседнюю ячейку (В3) введем формулу: =ЕСЛИ(B3=0;A3;B3-(-B3+СТЕПЕНЬ(B3;3)-1/11)).

В ячейке С3 проконтролируем значение f (x): с помощью формулы =B3-СТЕПЕНЬ(B3;3)+1.

Корень уравнения – 1,179. Введем в ячейку А3 значение 2. Получим тот же результат:

Корень на заданном промежутке один.