Лекция 3 - численные методы. Логические функции от двух переменных

Логические функции от двух переменных

Пусть п = 2. Существует 16 различных логических функций от двух переменных. Рассмотрим их подробно:

Аргу-менты

Функции

X1

X2

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

F₁ — константа 0.

F₂ — конъюнкция.

F₃ — отрицательные импликации X₁ и X₂.

F₄ — функция, повторяющая переменная X₁.

F₅ — отрицание импликации X₂ и X₁.

F₆ — переменная X₂.

F₇ — строгая дизъюнкция или отрицание эквивалентности
(неравнозначность) переменных X₁ и X₂. Значение этой функции получается поразрядным сложением двоичных переменных X₁ и X₂ по модулю 2, то есть без учета переноса в старший разряд.

F₈ — дизъюнкция.

F₉ — отрицание дизъюнкции (функция ИЛИ-НЕ); эта функция называется также функцией Пирса («стрелка» Пирс).

F₁₀ — эквивалентность.

F₁₁ — отрицание переменной X₂.

F₁₂ — импликация X₁ и X₂.

F₁₃ — отрицание X₁.

F₁₄ —импликация X₁ и X₂.

F₁₅ — отрицание конъюнкции (функция И-НЕ); эта функция называется также функцией Шеффера («штрих» Шеффера).

F₁₆ — константа 1.

С увеличением числа аргументов количество логических функций резко возрастает. Так, при п = 3 их будет уже 256. Но изучать их все нет никакой необходимости. Дело в том, что функция любого количества переменных может быть выражена через функции только двух переменных. Делается это с помощью приема суперпозиции, состоящего в том, что, во-первых, на место переменных подставляются функции, во-вторых, переменные меняются местами.

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

Вот несколько примеров функционально полных наборов:

1) F2 и F11; 2) F13 и F8; 3) F9 и F15.

При желании всю алгебру логики можно свести к одной функции. Но чаще всего логические функции записываются в виде логического выражения через инверсию, конъюнкцию и дизъюнкцию.

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

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

Решение систем линейных уравнений.

(4.1)

Дана система линейных уравнений (СЛУ) с n неизвестными:

В матричной форме записи система (4.1) имеет вид:

(4.2)

где: n – порядок системы;

– матрица коэффициентов системы;

– вектор свободных членов; – вектор неизвестных;

В свернутой форме записи СЛУ имеет вид:

(4.3)

Система называется обусловленной (не вырожденной, не особенной), если определитель системы DA ¹ 0, и тогда система (4.1) имеет единственное решение.

Система называется не обусловленной (вырожденной, особенной), если DA = 0, и тогда система (4.1) не имеет решений или имеет бесконечное множество решений.

На практике коэффициенты системы a_ij и свободные члены b_i часто задаются приближенно, с некоторой неустранимой погрешностью. Поэтому, кроме существования и единственности решения СЛУ, важно еще знать, как влияет такая погрешность на получаемое решение.

Система называется плохо обусловленной, если неустранимая погрешность оказывает сильное влияние на решение; у таких систем определитель близок, но не равен 0.

Рассмотрим пример плохо обусловленной системы.

Дана система

Решение ;

Пусть b₂ имеет неустранимую погрешность %.

Если b2 = 1,01, то

Если b2 = 0,99, то

Решение изменяется очень сильно, следовательно, система плохо обусловлена, о чем говорит значение её определителя.

Рассмотрим геометрическую иллюстрацию обусловленности СЛУ на примере системы двух уравнений с двумя неизвестными:

a₁₁ x₁+ a₁₂ x₂ = b₁ уравнение (I)

a₂₁ x₁+ a₂₂ x₂= b₂ уравнение (II)

Рис. 3.1. Геометрическая иллюстрация обусловленности СЛУ.

Каждому уравнению в плоскости (x₁,x₂) соответствует прямая, а точка пересечения этих прямых является решением этой системы. Если ΔA = 0, то наклоны прямых одинаковы, и они либо параллельны (т.е. не имеют решения), либо совпадают (имеют бесконечное множество решений). Если ΔA ¹ 0, то прямые имеют единственную точку пересечения.

Но если система плохо обусловлена (∆А≈0), даже незначительное изменение одного из коэффициентов приведет к сильному изменению решения системы, т.к. прямые почти параллельны.

Для решения СЛУ широко применяться прямые и итерационные методы. Область применения некоторых из них показана в таблице.

Тип	Название метода	Число арифметических действий (при n = 20)	Область примененения
Прямые	Формулы Крамера	~ ()	n<5
Исключения Гаусса	~ (5733)	n<200
Итерационные	Простых итераций	~ n² на каждой итерации (400n)	до 10^5
Гаусса-Зейделя

Современная супер-ЭВМ имеет производительность 30 терафлоп – 30·10¹² операций с вещественными числами в секунду. Такой машине для решения СЛУ для n=20 по формуле Крамера требуется:

года.

На решение СЛУ прямым методом сильное влияние оказывает погрешность округления, т.к. требуется огромное количество арифметических действий.

На решение СЛУ итерационным методом погрешность округления практически не влияет, но не всегда удается обеспечить сходимость итерационного процесса.

3.1. Формулы Крамера.

x_i^* = DA_i / DA, i = 1, n, 1 (4.4)

где A_i – вспомогательная матрица, полученная из A заменой i-го столбца вектором свободных членов.

Пример 4.1. Решить СЛУ, используя формулы Крамера.

x₁ + 5×x₂ - x₃ = 2

x₁ 2×x₃ = -1

2×x₁ - x₂ – 3×x₃ = 5

Вычислим определители по правилу треугольников:

DA = = 0 + 1 + 20 + 0 + 15 + 2 = 38 – система обусловлена.

DA₁ = = 0 + 50 - 1 - 0 + 4 - 15 = 38

DA₂ = = 3 + 8 – 5 – 2 + 6 - 10 = 0

DA₃ = = 0 - 10 – 2 – 0 -25 - 1 = -38

Вычислим решения:

x₁^* = DA₁ / DA = 38/38 = 1;

x₂^* = DA₂ / DA = 0/38 = 0;

x₃^* = DA₃ / DA =-38/38 = -1.

Проверим полученное решение подстановкой в исходную систему.

1 + 5×0 – (-1) = 2

1 + 2×(-1) = -1

2×1 – 0 – 3×(-1) = 5

Система обращается в тождество, решение верное.

Формулы Крамера применяться редко, только для n≤4.

3.2. Метод исключений Гаусса.

Решим рассмотренную ранее систему (пример 4.1) методом исключения Гаусса.

Пример 3.2. Решение проводиться в два этапа.

1 этап Прямой ход - матрица A преобразуется к треугольному виду: путем эквивалентных линейных преобразований уравнений системы поддиагональные коэффициенты матрицы А обнуляются.

x₁ + 5×x₂ - x₃ = 2

x₁ 2×x₃ = -1

2×x₁ - x₂ – 3×x₃ = 5

Исключим x1 из 2-го и 3-го уравнения: ко 2-му уравнению прибавим 1-ое, умноженное на (-1); к 3-му уравнению прибавим 1-ое, умноженное на (-2).

x₁ + 5×x₂ - x₃ = 2

- 5×x₂ + 3×x₃ = -3

- 11×x₂ – x₃ = 1

Исключим x₂ из 3-го уравнения: к 3-му уравнению прибавим 2-ое, умноженное на (-11/5). Полученный вид системы после прямого хода

x₁ + 5×x₂ - x₃ = 2

- 5×x₂ + 3×x₃ = -3

– 38/5×x₃ = 38/5

2 этап Обратный ход - вычисляются значения неизвестных, начиная с последнего уравнения:

x₃^* = -1

-5×x₂ + 3×x₃^*=-3 Þ x₂^*=(3 + 3×x₃^*)=(3 + 3×(-1))=0

x₁ +5×x₂^* - x₃^*=2 Þ x₁^*=2 + 5×x₂^* + x₃^*=2 + 5×0 + (-1)=1

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

Словесное описание алгоритма метода исключения Гаусса. Схема алгоритма приведена на рисунках 4.1-4.6.

Алгоритм прямого хода:

Шаг 1. Примем k=1

Шаг 2. Выбираем рабочую строку.

Если a_kk ≠ 0, то k-ая строка – рабочая.

Если нет, меняем k-ю строку на m-ю (n≥m>k), в которой a_mk ≠ 0, . Если такой строки нет, система вырожденная, решение прекратить.

Шаг 3. Для строк i=k+1, k+2, …, n вычисляются новые значения коэффициентов.

, , и новые правые части

Шаг 4. Увеличиваем k = k + 1. Если k = n, прямой ход завершен, иначе алгоритм повторяется со второго шага.

Получаем верхнюю треугольную матрицу А:

,

Алгоритм обратного хода:

Шаг 1. Вычислим

Шаг 2. Вычислим:

,

Основной алгоритм решения СЛУ методом исключения Гаусса.

Рис. 3.1. Основной алгоритм решения СЛУ методом исключения Гаусса.

Для контроля правильности решения нужно считать невязки δ_i по формуле (4.5).

δ_i, (4.5)

Если невязки велики, задача решена неверно. Причиной может быть сбой машины (крайне редко), ошибки в программе, погрешность округления (при большом n и когда DA = detA = 0- система плохо обусловлена).

Разновидности метода исключения:

а) Метод исключения Гаусса с выбором главного элемента в столбце.

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

,

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

б) Метод Гаусса-Жордана.

В алгоритм прямого хода нужно внести следующие изменения:

- на шаге 3

- на шаге 4 прямой ход завершиться при достижении условия k>n.

Вид матрицы коэффициентов после прямого хода

Упрощается обратный ход: x_i =b_i / a_i,i, i =1,2,…,n

Недостаток метода – увеличение общего числа действий, и соответственно, влияния погрешности округления.

Рис. 3. Алгоритм запоминания коэффициентов.

Рис. 3.2. Алгоритм прямого хода

Рис. 4.6. Алгоритм расчета невязок

Рис. 3.5. Алгоритм обратного хода.

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

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

Рассмотрим особенности решения СЛУ методом простых итераций на примере.

Пример 4.3. Требуется найти решение системы с точностью ε=0,001.

x₁ + 5×x₂ - x₃ = 2

x₁ 2×x₃ = -1

2×x₁ - x₂ – 3×x₃ = 5

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

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

В первом уравнении исходной системы коэффициент при х₂ больше суммы модулей других коэффициентов: 5> 1+1. Поэтому это уравнение в новой системе нужно записать вторым уравнением. Для получения нового первого уравнения можно второе уравнение умножить на 2 и сложить с третьим уравнением. Для получения нового третьего уравнения можно из третьего уравнения вычесть второе.

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

Важно отметить, что подобные преобразования не меняют решения системы.

Выразим явно из каждого нового уравнения очередное неизвестное – получим формулы итерационного процесса.

Возьмем любое начальное приближение , например .

Вычислим новое приближение решения , подставив в правую часть начальное приближение:

Оценим достигнутую точность δ по формуле:

Итерационный процесс нужно продолжить, т.к. δ > ε.

Вычислим второе приближение , подставив в правую часть первое приближение:

Третье приближение:

Четвертое приближение:

Очевидно, что итерационный процесс сходиться, т.к. значение δ монотонно убывает. Для достижения требуемой точности ε=0,001 потребуется еще несколько итераций.

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

Основные расчетные зависимости метода простых итераций:

Формула итерационного процесса:

, (3.6)

где: k = 1, 2, … – номер приближения.

– начальное приближение, ;

Условия завершения итерационного процесса:

d£e (3.7)

где e – требуемая точность;

d – оценка достигнутой точности, (3.8)

или (3.9)

Условие сходимости итерационного процесса (условие преобладания диагональных коэффициентов):

(3.10)

Схема алгоритма метода представлена на рис. 4.7.

Если в полученных результатах значения δ > e и k > k_max, то задача не решена, т.е. x(1:n) не является решением системы. Необходимо проверить условия сходимости или увеличить k_max.

3.4 Метод Гаусса-Зейделя

В формуле итерационного процесса метода простых итераций (4.6) к моменту вычисления x_i^(k) уже вычислены значения x₁^(k),x₂^(k),...,x_i-1^(k).

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

(3.11)

Условие завершения итерационного процесса (4.7) и условия сходимости (4.10) справедливы и для данного метода. Поэтому схема алгоритма Гаусса-Зейделя отлична только формулой расчета нового приближения:

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

Достоинства итерационных методов:

1. Погрешность округления не накапливается от итерации к итерации.

2. Число итераций при n>100 обычно меньше n, поэтому общее число действий меньше n³, т.е. меньше, чем в методе исключений Гаусса.

3. Не требуется больший объем памяти.

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

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

Дата добавления: 2014-01-11