Метод неопределенных коэффициентов

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

Рассмотрим случай трех переменных. Булева функция в ДНФ может быть представлена в виде всевозможных конъюнктивных членов, которые могут входить в ДНФ:

где kО{0,1} ‑ коэффициенты. Метод заключается в подборе коэффициентов таким образом, чтобы получаемая ДНФ была минимальной.

Если теперь задать всевозможные значения переменных от 000 до 111, то получим 2 n (2 3 =8) уравнений для определения коэффициентов k :

Рассматривая наборы, на которых функция принимает нулевое значение, определяют коэффициенты, которые равны 0, и вычеркивают их из уравнений, в правой части которых стоит 1. Из оставшихся коэффициентов в каждом уравнении к единице приравнивают по одному коэффициенту, определяющему конъюнкцию наименьшего ранга. Остальные коэффициенты приравнивают к 0. Итак, единичные коэффициенты k определяют соответствующую минимальную форму.

Пример . Минимизировать заданную функцию

если известны значения: ; ; ; ; ; ; ; .

Решение.

После вычеркивания нулевых коэффициентов получим:

=1;

=1;

=1.

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

Ответ : вид минимизированной функции .

Следует отметить, что метод неопределенных коэффициентов эффективен, когда число переменных невелико и не превышает 5-6.

Многомерный куб

Рассмотрим графическое представление функции в виде многомерного куба. Каждой вершине n -мерного куба можно поставить в соответствие конституенту единицы.

Подмножество отмеченных вершин является отображением на n -мерном кубе булевой функции от n переменных в СДНФ.

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

Минитерм (n-1)-го ранга можно рассматривать как результат склеивания двух минитермов n -го ранга, т.е.

На n -мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координат х i , соединяющих эти вершины ребром (говорят, что ребро покрывает инцидентные ему вершины).

Таким образом, минитермам (n -1)-го порядка соответствуют ребра n-мерного куба.

Аналогично устанавливается соответствие минитермов (n -2)-го порядка граням n -мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).

Элементы n -мерного куба, характеризующиеся S измерениями, называются S -кубами.

Так вершины являются 0-кубами, ребра 1-кубами, грани 2-кубами и т.д.

Обобщая, можно сказать, что минитерм (n-S ) ранга в ДНФ для функции n переменных отображается S -кубом, причем каждый S -куб покрывает все те кубы низшей размерности, которые связаны только с его вершинами.

Пример. На рис. дано отображение

Здесь минитермы и соответствуют 1-кубам (S =3-2=1), а минитерм х 3 отображается 2-кубам (S =3-1=2).

Итак, любая ДНФ отображается на n -мерном кубе совокупностью S -кубов, которые покрывают все вершины, соответствующие конституентам единицам (0-куба).

Конституенты . Для переменных х 1 , х 2 ,… х n выражение называют конституентой единицы, а - конституентой нуля ( означает либо , либо ).

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

Например: конституенте единице соответствует набор (1011), а конституенте нуля - набор (1001).

Так как СД(К)НФ является дизъюнкцией (конъюнкцией) конституент единицы (нуля), то можно утверждать, что представляемая ею булева функция f (x 1 ,x 2 ,…,x n ) обращается в единицу (нуль) только при наборах значений переменных x 1 ,x 2 ,…,x n , соответствующих этим копституантам. На остальных наборах эта функция обращается в 0 (единицу).

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

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

Например, функции, заданной таблицей

соответствуют

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

Справедливо и обратное утверждение: если некоторая совокупность S -кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим S -кубам минитермов является выражением данной функции в ДНФ.

Говорят, что такая совокупность S -кубов (или соответствующих им минитермов) образует покрытие функции. Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число S -кубов которого было бы поменьше, а их размерность S - побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием.

Например, для функции у = покрытие соответствует неминимальной форме.

Данный сервис предназначен для разложения дроби вида:

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

Инструкция . Введите числитель и знаменатель дроби. Нажмите кнопку Решить.

При оформлении в качестве переменной использовать x t z u p λ

Примечание: Например, x 2 записывается как x^2 , (x-2) 3 пишем как (x-2)^3 . Между сомножителями ставим знак умножить (*) .

Правила ввода функции

Это поле предназначено для ввода числителя выражения
Общую переменную x необходимо предварительно вынести за скобки. Например, x 3 + x = x(x 2 + 1) или x 3 - 5x 2 + 6x = x(x 2 - 5x + 6) = x(x-3)(x-2).

Правила ввода функции

Это поле предназначено для ввода знаменателя выражения Например, x 2 записывается как x^2 , (x-2) 3 пишем как (x-2)^3 . Между сомножителями ставим знак умножить (*) .
Общую переменную x необходимо предварительно вынести за скобки. Например, x 3 + x = x(x 2 + 1) или x 3 - 5x 2 + 6x = x(x 2 - 5x + 6) = x(x-3)(x-2).

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

1. Разложение знаменателя на множители.
2. Разложение дроби в виде суммы простейших дробей с неопределенными коэффициентами.
3. Группировка числителя с одинаковыми степенями x .
4. Получение системы линейных алгебраических уравнений с неопределенными коэффициентами в качестве неизвестных.
5. Решение СЛАУ: методом Крамера , методом Гаусса , методом обратной матрицы или методом исключения неизвестных.

Пример . Используем метод разложения на простейшие. Разложим функцию на простейшие слагаемые:


Приравняем числители и учтем, что коэффициенты при одинаковых степенях х , стоящие слева и справа должны совпадать
2x-1 = A(x+2) 2 (x-4) + Bx(x+2) 2 (x-4) + Cx(x-4) + Dx(x+2) 2
A + B = 0
-12A -8B -4C + 4D = 2
-16A = -1
0A -2B + C + 4D = 0
Решая ее, находим:
A = 1 / 16 ;B = - 1 / 9 ;C = - 5 / 12 ;D = 7 / 144 ;

Интегрирование дробно-рациональной функции.
Метод неопределенных коэффициентов

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

Как ни странно, сейчас мы будем заниматься не столько нахождением интегралов, сколько… решением систем линейных уравнений. В этой связи настоятельно рекомендую посетить урок А именно – нужно хорошо ориентироваться в методах подстановки («школьном» методе и методе почленного сложения (вычитания) уравнений системы).

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

Интегрирование правильной дробно-рациональной функции

Сразу пример и типовой алгоритм решения интеграла от дробно-рациональной функции.

Пример 1

Шаг 1. Первое, что мы ВСЕГДА делаем при решении интеграла от дробно-рациональной функции – это выясняем следующий вопрос: является ли дробь правильной? Данный шаг выполняется устно, и сейчас я объясню как:

Сначала смотрим на числитель и выясняем старшую степень многочлена:

Старшая степень числителя равна двум.

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

и мысленно умножаем: – таким образом, старшая степень знаменателя равна трём. Совершенно очевидно, что если реально раскрыть скобки, то мы не получим степени, больше трёх.

Вывод : Старшая степень числителя СТРОГО меньше старшей степени знаменателя, значит, дробь является правильной.

Если бы в данном примере в числителе находился многочлен 3, 4, 5 и т.д. степени, то дробь была бы неправильной .

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

Шаг 2. Разложим знаменатель на множители. Смотрим на наш знаменатель:

Вообще говоря, здесь уже произведение множителей, но, тем не менее, задаемся вопросом: нельзя ли что-нибудь разложить еще? Объектом пыток, несомненно, выступит квадратный трехчлен. Решаем квадратное уравнение:

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

Общее правило: ВСЁ, что в знаменателе МОЖНО разложить на множители – раскладываем на множители

Начинаем оформлять решение:

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

Смотрим на нашу подынтегральную функцию:

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

Возникает вопрос, а можно ли вообще так сделать? Вздохнем с облегчением, соответствующая теорема математического анализа утверждает – МОЖНО. Такое разложение существует и единственно .

Только есть одна загвоздочка, коэффициенты мы пока не знаем, отсюда и название – метод неопределенных коэффициентов.

Как вы догадались, последующие телодвижения так, не гоготать! будут направлены на то, чтобы как раз их УЗНАТЬ – выяснить, чему же равны .

Будьте внимательны, подробно объясняю один раз!

Итак, начинаем плясать от:

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

Теперь благополучно избавляемся от знаменателей (т.к. они одинаковы):

В левой части раскрываем скобки, неизвестные коэффициенты при этом пока не трогаем:

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

С точки зрения понятного объяснения коэффициенты лучше внести в скобки (хотя лично я никогда этого не делаю в целях экономии времени):

Составляем систему линейных уравнений.
Сначала разыскиваем старшие степени:

И записываем соответствующие коэффициенты в первое уравнение системы:

Хорошо запомните следующий нюанс . Что было бы, если б в правой части вообще не было ? Скажем, красовалось бы просто без всякого квадрата? В этом случае в уравнении системы нужно было бы поставить справа ноль: . Почему ноль? А потому что в правой части всегда можно приписать этот самый квадрат с нулём: Если в правой части отсутствуют какие-нибудь переменные или (и) свободный член, то в правых частях соответствующих уравнений системы ставим нули .

Записываем соответствующие коэффициенты во второе уравнение системы:

И, наконец, минералка, подбираем свободные члены.

Эх,…что-то я расшутился. Шутки прочь – математика наука серьезная. У нас в институтской группе никто не смеялся, когда доцент сказала, что разбросает члены по числовой прямой и выберет из них самые большие. Настраиваемся на серьезный лад. Хотя… кто доживет до конца этого урока, все равно будет тихо улыбаться.

Система готова:

Решаем систему:

(1) Из первого уравнения выражаем и подставляем его во 2-е и 3-е уравнения системы. На самом деле можно было выразить (или другую букву) из другого уравнения, но в данном случае выгодно выразить именно из 1-го уравнения, поскольку там самые маленькие коэффициенты .

(2) Приводим подобные слагаемые во 2-м и 3-м уравнениях.

(3) Почленно складываем 2-е и 3-е уравнение, при этом, получая равенство , из которого следует, что

(4) Подставляем во второе (или третье) уравнение, откуда находим, что

(5) Подставляем и в первое уравнение, получая .

Если возникли трудности с методами решения системы отработайте их на уроке Как решить систему линейных уравнений?

После решения системы всегда полезно сделать проверку – подставить найденные значения в каждое уравнение системы, в результате всё должно «сойтись».

Почти приехали. Коэффициенты найдены, при этом:

Чистовое оформление задание должно выглядеть примерно так:

Как видите, основная трудность задания состояла в том, чтобы составить (правильно!) и решить (правильно!) систему линейных уравнений. А на завершающем этапе всё не так сложно: используем свойства линейности неопределенного интеграла и интегрируем. Обращаю внимание, что под каждым из трёх интегралов у нас «халявная» сложная функция, об особенностях ее интегрирования я рассказал на уроке Метод замены переменной в неопределенном интеграле .

Проверка: Дифференцируем ответ:

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

Пример 2

Найти неопределенный интеграл.

Вернемся к дроби из первого примера: . Нетрудно заметить, что в знаменателе все множители РАЗНЫЕ. Возникает вопрос, а что делать, если дана, например, такая дробь: ? Здесь в знаменателе у нас степени, или, по-математически кратные множители . Кроме того, есть неразложимый на множители квадратный трехчлен (легко убедиться, что дискриминант уравнения отрицателен, поэтому на множители трехчлен никак не разложить). Что делать? Разложение в сумму элементарных дробей будет выглядеть наподобие с неизвестными коэффициентами вверху или как-то по-другому?

Пример 3

Представить функцию

Шаг 1. Проверяем, правильная ли у нас дробь
Старшая степень числителя: 2
Старшая степень знаменателя: 8
, значит, дробь является правильной.

Шаг 2. Можно ли что-нибудь разложить в знаменателе на множители? Очевидно, что нет, всё уже разложено. Квадратный трехчлен не раскладывается в произведение по указанным выше причинам. Гуд. Работы меньше.

Шаг 3. Представим дробно-рациональную функцию в виде суммы элементарных дробей.
В данном случае, разложение имеет следующий вид:

Смотрим на наш знаменатель:
При разложении дробно-рациональной функции в сумму элементарных дробей можно выделить три принципиальных момента:

1) Если в знаменателе находится «одинокий» множитель в первой степени (в нашем случае ), то вверху ставим неопределенный коэффициент (в нашем случае ). Примеры №1,2 состояли только из таких «одиноких» множителей.

2) Если в знаменателе есть кратный множитель , то раскладывать нужно так:
– то есть последовательно перебрать все степени «икса» от первой до энной степени. В нашем примере два кратных множителя: и , еще раз взгляните на приведенное мной разложение и убедитесь, что они разложены именно по этому правилу.

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

На самом деле, есть еще 4-й случай, но о нём я умолчу, поскольку на практике он встречается крайне редко.

Пример 4

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

Это пример для самостоятельного решения. Полное решение и ответ в конце урока.
Строго следуйте алгоритму!

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

Пример 5

Найти неопределенный интеграл.

Шаг 1. Очевидно, что дробь является правильной:

Шаг 2. Можно ли что-нибудь разложить в знаменателе на множители? Можно. Здесь сумма кубов . Раскладываем знаменатель на множители, используя формулу сокращенного умножения

Шаг 3. Методом неопределенных коэффициентов разложим подынтегральную функцию в сумму элементарных дробей:

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

Приводим дробь к общему знаменателю:

Составим и решим систему:

(1) Из первого уравнения выражаем и подставляем во второе уравнение системы (это наиболее рациональный способ).

(2) Приводим подобные слагаемые во втором уравнении.

(3) Почленно складываем второе и третье уравнения системы.

Все дальнейшие расчеты, в принципе, устные, так как система несложная.

(1) Записываем сумму дробей в соответствии с найденными коэффициентами .

(2) Используем свойства линейности неопределенного интеграла. Что произошло во втором интеграле? С этим методом Вы можете ознакомиться в последнем параграфе урока Интегрирование некоторых дробей .

(3) Еще раз используем свойства линейности. В третьем интеграле начинаем выделять полный квадрат (предпоследний параграф урока Интегрирование некоторых дробей ).

(4) Берём второй интеграл, в третьем – выделяем полный квадрат.

(5) Берём третий интеграл. Готово.

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

Пример 1. Шаг 2.

.

Умножаем неопределённые коэффициенты на многочлены, которых нет в данной отдельной дроби, но которые есть в других полученных дробях:

Раскрываем скобки и приравниваем полученое к полученному выражению числитель исходной подынтегральной дроби:

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

.

Сокращаем все иксы и получаем эквивалентную систему уравнений:

.

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

.

Пример 2. Шаг 2. На шаге 1 получили следующее разложение исходной дроби на сумму простых дробей с неопределёнными коэффициентами в числителях:

.

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

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

Решаем полученную систему:

Итак, , отсюда

.

Пример 3. Шаг 2. На шаге 1 получили следующее разложение исходной дроби на сумму простых дробей с неопределёнными коэффициентами в числителях:

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

Как и в предыдущих примерах составляем систему уравнений:

Сокращаем иксы и получаем эквивалентную систему уравнений:

Решая систему, получаем следующие значения неопределённых коэффициентов:

Получаем окончательное разложение подынтегральной дроби на сумму простых дробей:

.

Пример 4. Шаг 2. На шаге 1 получили следующее разложение исходной дроби на сумму простых дробей с неопределёнными коэффициентами в числителях:

.

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

Решая систему, получаем следующие значения неопределённых коэффициентов:

Получаем окончательное разложение подынтегральной дроби на сумму простых дробей:

Пример 5. Шаг 2. На шаге 1 получили следующее разложение исходной дроби на сумму простых дробей с неопределёнными коэффициентами в числителях:

.

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

Решая систему, получаем следующие значения неопределённых коэффициентов:

.

Получаем окончательное разложение подынтегральной дроби на сумму простых дробей:

.

Пример 6. Шаг 2. На шаге 1 получили следующее разложение исходной дроби на сумму простых дробей с неопределёнными коэффициентами в числителях:

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

Решая систему, получаем следующие значения неопределённых коэффициентов:

.

Получаем окончательное разложение подынтегральной дроби на сумму простых дробей:

.

Пример 7. Шаг 2. На шаге 1 получили следующее разложение исходной дроби на сумму простых дробей с неопределёнными коэффициентами в числителях:

.

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

Решая систему, получаем следующие значения неопределённых коэффициентов:

Получаем окончательное разложение подынтегральной дроби на сумму простых дробей:

.

Пример 8. Шаг 2. На шаге 1 получили следующее разложение исходной дроби на сумму простых дробей с неопределёнными коэффициентами в числителях:

.

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