Решение линейных уравнений методом простой итерации c помощью программы Microsoft Excel. Решение слау методом якоби (метод простых итераций) с использованием приложения microsoft excel

Дана система n алгебраических уравнений сn неизвестными:

Эту систему можно записать в матричном виде:
,

;;.

где A - квадратная матрица коэффициентов,X - вектор-столбец неизвестных,B - вектор-столбец свободных членов.

Численные методы решения систем линейных уравнений делятся на прямые и итерационные. Первые используют конечные соотношения для вычисления неизвестных. Пример - метод Гаусса. Вторые основаны на последовательных приближениях. Примеры - метод простой итерации и метод Зейделя.

1. Метод Гаусса

Метод основан на приведении матрицы системы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы. Сначала с помощью первого уравнения исключается x 1 из всех последующих уравнений. Затем с помощью второго уравнения исключаетсяx 2 из последующих и т.д. Этот процесс называется прямым ходом метода Гаусса и продолжается до тех пор, пока в левой части последнегоn -го уравнения не останется лишь один член с неизвестнымx n . В результате прямого хода система принимает вид:

(2)

Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных, начиная с x n и кончаяx 1 .

1. Метод простой итерации и метод Зейделя

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

.

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

(3)

где k - номер итерации, - заданная точность.

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

(4)

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

(5)

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

(6)

3.4. Реализация в пакете Excel

В качестве примера рассмотрим систему уравнений:

Данная система удовлетворяет условию сходимости и может быть решена как прямыми, так и итерационными методами. Последовательность действий (рис.7):

Оформить заголовок в строке 1 «Численные методы решения систем линейных уравнений».

В области D3:H6 ввести исходные данные, как показано на рисунке.

Ввести в ячейку F8 текст заголовка «Метод Гаусса» (выравнивание по центру).

Скопировать исходные данные E4:H6 в областьB10:E12. Это - исходные данные для прямого хода метода Гаусса. Обозначим соответствующие строкиA1,A2 иA3.

Подготовить место для первого прохода, обозначив в области G10:G12 названия строкB1,B2 иB3.

Ввести в ячейку H10 формулу «=B10/$B$10». Скопировать эту формулу на ячейкиI10:K10. Это - нормировка на коэффициентa 11 .

Ввести в ячейку H11 формулу «=B11-H10*$B$11». Скопировать эту формулу на ячейкиI11:K11.

Ввести в ячейку H12 формулу «=B12-H10*$B$12». Скопировать эту формулу на ячейкиI12:K12.

Подготовить место для второго прохода, обозначив в области A14:A16 названия строкC1,C2 иC3.

Ввести в ячейку B14 формулу «=H10». Скопировать эту формулу на ячейкиC14:E14.

Ввести в ячейку B15 формулу «=H11/$I$11». Скопировать эту формулу на ячейкиC15:E15.

12. Ввести в ячейку В16 формулу «=Н12-В15*$I$12». Скопировать эту форму­лу на ячейки С16:Е16.

13. Подготовить место для третьего прохода, обозначив в области G14:G16 на­звания строк D1, D2 и D3.

14. Ввести в ячейку H14 формулу «=В14». Скопировать эту формулу на ячейки I14:К14.

15. Ввести в ячейку H15 формулу «=В15». Скопировать эту формулу на ячейки I15:К15.

16. Ввести в ячейку Н16 формулу «=B16/$D$16». Скопировать эту формулу на ячейки I16:К16.

17. Подготовить место для обратного хода метода Гаусса, введя в ячейки В18, E18 и H18 соответствующие тексты «х3=», «х2=» и «х1=».

18. Ввести в ячейку С18 формулу «=К16». Получим значение переменной х 3.

19. Ввести в ячейку F18 формулу «=К15-J15*К16». Получим значение перемен­нойх 2.

20.Ввести в ячейку I18 формулу «=K10-I10*F18-J10*C18». Получим значение переменнойх 1.

21. Ввести в ячейку F21 текст заголовка «Метод простой итерации» (выравни­вание по центру).

22. Ввести в ячейку J21 текст «е=» (выравнивание по правому краю).

23. Ввести в ячейку К21 значение точности е (0,0001).

24. Обозначить в области А23:А25 названия переменных.

25. В области В23:В25 задать начальные значения переменных (нули).

26. Ввести в ячейку С23 формулу «=($H$4-$F$4*B24-$G$4*B25)/$E$4». Полу­чим значение переменной х 1 на первой итерации.

27. Ввести в ячейку С24 формулу «=($H$5-$E$5*B23-$G$5*B25)/$F$5». Полу­чим значение переменной х 2 на первой итерации.

28. Ввести в ячейку С25 формулу «=($H$6-$E$6*B23-$F$6*B24)/$G$6». Полу­чим значение переменной х 3 на первой итерации.

29. Ввести в ячейку С26 формулу «=ЕСЛИ(АВS(С23-В23)>$К$21;" "; ЕСЛИ(АВS(С24-В24)>$К$21;" ";ЕСЛИ(АВS(С25-В25)>$К$21;" "; ""корни")))». Это - проверка на достижение заданной точности (при этом печата­ется сообщение «корни»).

30. Выделить диапазон С23:С26 и скопировать его до столбца К, используя при­ем протаскивания. При появлении в строке 26 сообщения «корни» соответст­вующий столбец будет содержать приближенные значения переменных х 1,x 2, x 3, которые являются решением системы уравнений с заданной точно­стью.

31. В области А27:К42 построить диаграмму, показывающую процесс прибли­жения значений переменных х 1,х 2,x 3 к решению системы. Диаграмма стро­ится в режиме «График», где по оси абсцисс откладывается номер итерации.

32. Ввести в ячейку F43 текст заголовка «Метод Зейделя» (выравнивание по центру).

33. Ввести в ячейку J43 текст «е=» (выравнивание по правому краю).

34. Ввести в ячейку К43 значение точности е(0,0001).

35. Обозначить в области А45:А47 названия переменных.

36. В области В45:В47 задать начальные значения переменных (нули).

37.Ввести в ячейку С45 формулу «=($H$4-$F$4*B46-$G$4*B47)/$E$4». Полу­чим значение переменной х 1 на первой итерации.

38.Ввести в ячейку С46 формулу «=($H$5-$E$5*C45-$G$5*B47)/$F$5». Полу­чим значение переменной х 2 на первой итерации.

39. Ввести в ячейку С47 формулу «=($H$6-$E$6*C45-$F$6*C46)/$G$6». Полу­чим значение переменной x 3 ,на первой итерации.

40. Ввести в ячейку С48 формулу «=ЕСЛИ(АВ5(С45-В45)>$К$43;" "; ЕСЛИ(АВS(С46-В46)>$К$43;" ";ЕСЛИ{АВS(С47-В47)>$К$43;" ";"кор­ни")))».

41. Выделить диапазон С45:С48 и скопировать его до столбца К, используя при­ем протаскивания. При появлении в строке 26 сообщения «корни» соответст­вующий столбец будет содержать приближенные значения переменных х 1,х 2,x 3, которые являются решением системы уравнений с заданной точно­стью. Видно, что метод Зейделя сходится быстрее, чем метод простой итера­ции, то есть заданная точность здесь достигается за меньшее число итераций.

42. В области А49:К62 построить диаграмму, показывающую процесс прибли­жения значений переменных х1, х2, x3 к решению системы. Диаграмма стро­ится в режиме «График», где по оси абсцисс откладывается номер итерации.

Напомню, что циклическая ссылка появляется, если в ячейку Excel введена формула, содержащая ссылку на саму эту ячейку (напрямую или через цепочку других ссылок). Например (рис. 1), в ячейке С2 находится формула, ссылающаяся на саму ячейку С2.

Но!.. Не всегда циклическая ссылка является бедствием. Циклическую ссылку можно использовать для решения уравнений итерационным способом. Для начала нужно позволить Excel`ю вести вычисления, даже при наличии циклической ссылки. В обычном режиме Excel, обнаружив циклическую ссылку, выдаст сообщение об ошибке, и потребует ее устранения. В обычном режиме Excel не может провести вычисления, так как циклическая ссылка порождает бесконечный цикл вычислений. Можно, либо устранить циклическую ссылку, либо допустить вычисления по формуле с циклической ссылкой, но ограничив число повторений цикла. Для реализации второй возможности щелкните на кнопке «Office» (в левом верхнем углу), а затем на «Параметры Excel» (рис. 2).

Скачать заметку в формате , примеры в формате

Рис. 2. Параметры Excel

В открывшемся окне «Параметры Excel» перейдите на вкладку Формулы и отметьте «Включить итеративные вычисления» (рис. 3). Помните, что эта опция включается для приложения Excel в целом (а не для одного файла), и будет действовать, пока вы ее не отключите.

Рис. 3. Включить итеративные вычисления

На этой же вкладе, можно выбрать, как будут вестись вычисления: автоматически или вручную. При автоматическом вычислении Excel сразу рассчитает конечный результат, при вычислениях, вручную, можно будет наблюдать результат каждой итерации (простым нажатием F9 запуская каждый новый цикл вычисления).

Решим уравнение третьей степени: х 3 – 4х 2 – 4х + 5 = 0 (рис. 4). Для решения этого уравнения (и любого другого уравнения совершенно произвольного вида) понадобится всего одна ячейка Excel.

Рис. 4. График функции f(x)

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

(1) x = x – f(x)/f’(x), где

х – переменная;

f(x) – функция, задающая уравнение, корни которого мы ищем; f(x) = х 3 – 4х 2 – 4х + 5

f’(x) – производная нашей функции f(x); f’(x) = 3х 2 – 8х – 4; производные основных элементарных функций можно посмотреть .

Если вы заинтересовались, откуда взялась формула (1), можете почитать, например, .

Итоговая рекуррентная формула имеет вид:

(2) х = x – (х 3 – 4х 2 – 4х + 5)/(3х 2 – 8х – 4)

Выберем любую ячейку на листе Excel (рис. 5; в нашем примере это ячейка G19), присвоим ей имя х , и введем в нее формулу:

(3) =x-(x^3-4*x^2-4x+5)/(3*x^2-8*x-4)

Можно вместо х использовать адрес ячейки… но согласитесь, что имя х , смотрится привлекательнее; следующую формулу я ввел в ячейку G20:

(4) =G20-(G20^3-4*G20^2-4*G20+5)/(3*G20^2-8*G20-4)

Рис. 5. Рекуррентная формула: (а) для поименованной ячейки; (б) для обычного адреса ячейки

Как только мы введем формулу и нажмем Enter, в ячейке сразу же появится ответ – значение 0,77. Это значение соответствует одному из корней уравнения, а именно второму (см. график функции f(x) на рис. 4). Поскольку начальное приближение не задавалось, итерационный вычислительный процесс начинался со значения, по умолчанию хранимого в ячейке х и равного нулю. Как же получить остальные корни уравнения?

Для изменения стартового значения, с которого рекуррентная формула начинает свои итерации, предлагается использовать функцию ЕСЛИ:

(5) =ЕСЛИ(x=0;-5;x-(x^3-4*x^2-4*x+5)/(3*x^2-8*x-4))

Здесь значение «-5» – начальное значение для рекуррентной формулы. Изменяя его, можно выйти на все корни уравнения.

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

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

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

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

Найти точные значения корней можно лишь в исключительных случаях. Как правило, используются методы приближенного вычисления корней с заданной степенью точности Е. Это означает, что если установлено, что искомый корень лежит внутри интервала , где 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.

В программе 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. Получим тот же результат:

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