Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Легко и непринужденно сворачивая ряд 1+х+х^2… в 1/(1-х), ни разу не упомянуто о том, что это верно лишь для |х|<=1.
В том-то и дело, что это здесь никого не интересует:
Тот факт, что ряд является формальным, говорит о том, что z — является просто символом, вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.
Ну так данный конкретный ряд сворачивается только для чисел, при чем по модулю меньших единицы. По формуле геом. прогрессии 1+х+х^2+..+х^n = (1-x^n)/(1-x). Если же предела х^n при n стремящемся к бесконечности нет или он не 0 (а его нет, если х — абстрактный предмет), то данный ряд не будет равен 1/(1-х).
Достаточно считать, что последовательность степенных рядов сходится к ряду S, если для любого N найдётся такой номер K, что у всех элементов последовательности с номерами больше K все коэффициенты до x^N включительно такие же, как у S. Тогда последовательность
1*(1-x), (1+x)*(1-x), (1+x+x^2)*(1-x),… сходится к 1. Объект x в этом случае быть числом не обязан, это просто символ.
1*(1-x), (1+x)*(1-x), (1+x+x^2)*(1-x),… сходится к 1. Объект x в этом случае быть числом не обязан, это просто символ.
Для тех, кто не понимает формальной строгости происходящего, я чуть-чуть дополню статью.
Наиболее правильный ответ на любые претензии по корректности: считайте, что вы работаете с формальными бесконечными рядами коэффициентов (a0, a1, a2,… ), как с бесконечномерным векторным пространством, на котором определено некоторым образом умножение (аналогично тому, как это происходит у многочленов: (a0, a1, a2, ...) * (b0, b1, b2) = (a0b0, a0b1 + a1b0, a2b0 + a1b1 + a0b2, ...) ), деление (чуть-чуть посложнее, но по-прежнему корректно, если младшие слагаемые в обоих рядах правильно соотносятся по степеням, то есть в итоге не вылезет слагаемых 1 / x), дифференцирование (опять же, по формальному правилу (a0, a1, a2, ...)' = (a1, 2a2, 3a3, ...), оно, например, удовлетворяет тождеству u'v = v'u), и так далее.
Одно из главных свойств заключается в том, что производящий ряд для функции f(x) очень часто совпадает с рядом Тейлора функции f. В частности это видно из статьи для функции 1 / (1 — x) = 1 + x + x^2 +… В ряд она действительно раскладывается только на круге сходимости (-1 < x < 1), но формальное равенство степенных рядов (1 — x) * (1 + x + x^2 + ...) = (1, -1, 0, 0, ...) * (1, 1, 1, 1, ...) = 1 по описанному выше правилу умножения верно само по себе.
Другой пример: разложение по биному для sqrt(1 + x) = (1 + x) ^ (1/2) = 1 + 1/2 x + 1/2 * (-1/2) / 2! x^2 + 1/2 * (-1/2) * (-3/2) / 3! x^3 +… = f(x) тоже удовлетворяет свойству sqrt(1 + x) * sqrt(1 + x) = 1 + x (проверьте сами, посчитав первые сколько-то коэффициентов в произведении).
Ну, и так далее. Аппарат действительно мощный. Очень наглядно иллюстрируется формулой для вывода чисел Каталана.
Наиболее правильный ответ на любые претензии по корректности: считайте, что вы работаете с формальными бесконечными рядами коэффициентов (a0, a1, a2,… ), как с бесконечномерным векторным пространством, на котором определено некоторым образом умножение (аналогично тому, как это происходит у многочленов: (a0, a1, a2, ...) * (b0, b1, b2) = (a0b0, a0b1 + a1b0, a2b0 + a1b1 + a0b2, ...) ), деление (чуть-чуть посложнее, но по-прежнему корректно, если младшие слагаемые в обоих рядах правильно соотносятся по степеням, то есть в итоге не вылезет слагаемых 1 / x), дифференцирование (опять же, по формальному правилу (a0, a1, a2, ...)' = (a1, 2a2, 3a3, ...), оно, например, удовлетворяет тождеству u'v = v'u), и так далее.
Одно из главных свойств заключается в том, что производящий ряд для функции f(x) очень часто совпадает с рядом Тейлора функции f. В частности это видно из статьи для функции 1 / (1 — x) = 1 + x + x^2 +… В ряд она действительно раскладывается только на круге сходимости (-1 < x < 1), но формальное равенство степенных рядов (1 — x) * (1 + x + x^2 + ...) = (1, -1, 0, 0, ...) * (1, 1, 1, 1, ...) = 1 по описанному выше правилу умножения верно само по себе.
Другой пример: разложение по биному для sqrt(1 + x) = (1 + x) ^ (1/2) = 1 + 1/2 x + 1/2 * (-1/2) / 2! x^2 + 1/2 * (-1/2) * (-3/2) / 3! x^3 +… = f(x) тоже удовлетворяет свойству sqrt(1 + x) * sqrt(1 + x) = 1 + x (проверьте сами, посчитав первые сколько-то коэффициентов в произведении).
Ну, и так далее. Аппарат действительно мощный. Очень наглядно иллюстрируется формулой для вывода чисел Каталана.
как с бесконечномерным векторным пространством, на котором определено некоторым образом умножение (аналогично тому, как это происходит у многочленов: (a0, a1, a2, ...) * (b0, b1, b2) = (a0b0, a0b1 + a1b0, a2b0 + a1b1 + a0b2, ...) )
Еще б доказать, что ничего никуда не вылезает за пределы кольца. То что существует деление, и можно определить дифференцирование.
В ряд она действительно раскладывается только на круге сходимости (-1 < x < 1), но формальное равенство степенных рядов (1 — x) * (1 + x + x^2 + ...) = (1, -1, 0, 0, ...) * (1, 1, 1, 1, ...) = 1 по описанному выше правилу умножения верно само по себе.
Но это лучше показать явно. Вы можете дать ссылку на учебник, где-это более строго расписывается?
Чувствую себя идиотом. Вроде как математика строгая и формальная, но куда не ткнись пытаются объяснять «интуитивно». Хотя, может просто не везло с преподами :)
Еще б доказать, что ничего никуда не вылезает за пределы кольца. То что существует деление, и можно определить дифференцирование.
То, что оно «не вылезает за пределы», следует из определения — результаты сложения и умножения записаны в виде степенных рядов, а значит, принадлежат описываемой структруре.
Чтобы доказать, что это кольцо, надо проверить основные свойства. То, что это группа по сложению, следует из того, что сложение идёт «покоординатно». То, что это векторное пространство над R (правда, без конструктивно описываемого базиса), нам сейчас неинтересно. Осталось проверить свойства умножения.
Коммутативность (которая не обязательна, но знать, выполняется ли она, полезно) сразу следует из формулы. Ассоциативность проверяем так же, как для матриц — явно выписывая коэффициент произведения трёх рядов: если d=a*b*c, то в обоих порядках получим d[i]=sum(a[k]*b[m]*c[n],k+m+n=i) — выражения будут одинаковыми. Дистрибутивность тоже проверяем прямым вычислением коэффициента.
Существование деления на ряд с ненулевым свободным членом доказывается по индукции: если мы вычислили первые N-1 коэффициент результата, то N-й определяется однозначно. И можно доказать, что каждый конкретный коэффициент произведения ряда с вычисленными таким образом коэффициентами на «делимое» будет равен соответствующему коэффициенту «делителя».
Про дифференцирование пока ничего не скажу. Для суммы и произведения формулы проверяются, а вот является ли подстановка одного степенного ряда в другой корректной операцией — не уверен. Думаю, что нет.
Показать явно здесь можно всё: просто садитесь и считайте. Прямо по исходным формулам. Но это долго и довольно скучно.
Если х это объект, то как вообще обосновать вот такое равенство 1/(1-x)=sum x^n?
Переписать его как (sum x^n)*(1-x)-1=0. И доказать, что коэффициент при любом x^k действительно равен нулю.
Спасибо! Очень понятно и кратко объяснили. Предыдущие комментарии не давали понимания.
Пожалуйста, объясните ещё, как в статье был совершён переход:
(1-z)G(z) = (1-z^4)(1+z^4)(1+z^8)…
в
(1-z)G(z) = 1
А как это доказать для любого z, в том числе не для чисел?
Мне кажется, тут нужно применить приём, похожий на тот, что применили Вы, поэтому задаю этот вопрос сюда.
Пожалуйста, объясните ещё, как в статье был совершён переход:
(1-z)G(z) = (1-z^4)(1+z^4)(1+z^8)…
в
(1-z)G(z) = 1
Моё доказательство для 0 < z < 1
Как я понял, (1-z^4)(1+z^4) превращается в (1-z^8), которое вместе с (1+z^8) превращается в (1-z^16) и т. д. Если предположить, что 0 < z < 1, то понятно, как в итоге получить 1. Можно взять последовательность, каждый следующий элемент которой будет получаться из предыдущего умножением на (1+z^(2^x)). Для неё доказать, что она возрастает, что для каждого y<1 найдётся номер члена, начиная с которого все члены будут больше y, и что все члены < 1. Тогда мы докажем, что предел такой последовательности 1. Возможно, есть и более простое доказательство.
А как это доказать для любого z, в том числе не для чисел?
Мне кажется, тут нужно применить приём, похожий на тот, что применили Вы, поэтому задаю этот вопрос сюда.
А у Вас уже почти всё написано. Произведение первых членов вплоть до 1+z^k равно 1-z^(2*k) (где k — степень двойки), а при умножении на любой следующий член коэффициенты произведения при z^0, z^1, ..., z^(2k-1) измениться уже не могут. Отсюда следует, что в бесконечном произведении все коэффициенты, кроме первого, равны нулю.
Действительно если ряд расходится это не значит, что он не имеет суммы.
Всем операциям которые мы проделывали над производящими функциями можно дать строгое истолкование как операциям над формальными рядами, а такие операции корректны даже если ряд расходится.
Но если мы говорим о просто степенных рядах, то конечно данная формула справедлива только для чисел меньших 1 по модулю.
Всем операциям которые мы проделывали над производящими функциями можно дать строгое истолкование как операциям над формальными рядами, а такие операции корректны даже если ряд расходится.
Но если мы говорим о просто степенных рядах, то конечно данная формула справедлива только для чисел меньших 1 по модулю.
А завтра как раз матан в НМУ… Спасибо!
Очень интересно было читать. Даже не догадывался о том, что ряды можно использовать таким необычным образом. Спасибо за интересное изложение:) Общая идея напомнила операционное исчисление.
любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.Казалось бы, это очевидным образом следует из существования двоичной системы счисления.
Спасибо за статью. Заставила залезть в учебник.
Но тут много неясных моментов. Без введения формальных алгебраических структур это напоминает шаманство.
1) С первых формул вводится деление, хотя это еще вопрос, допускает ли эта структура обратный элемент по произведению
2) Чудесным образом ряд раскладывается по сумме геометрической прогрессии. Но, как правильно заметили выше, это требует введения пределов. Аргумент что Z — это формальная переменная какой-то не очень «математический». Понятно, что сумма будет существовать, но лучше это показать или хотя б пояснить почему она существует.
Все же, вы можете дать строгое определение формального ряда, и вывести тоже самое без использование геометрической прогрессии (хотяб схематично)? А то есть чувство, что где-то обманывают :)
Но тут много неясных моментов. Без введения формальных алгебраических структур это напоминает шаманство.
1) С первых формул вводится деление, хотя это еще вопрос, допускает ли эта структура обратный элемент по произведению
2) Чудесным образом ряд раскладывается по сумме геометрической прогрессии. Но, как правильно заметили выше, это требует введения пределов. Аргумент что Z — это формальная переменная какой-то не очень «математический». Понятно, что сумма будет существовать, но лучше это показать или хотя б пояснить почему она существует.
Все же, вы можете дать строгое определение формального ряда, и вывести тоже самое без использование геометрической прогрессии (хотяб схематично)? А то есть чувство, что где-то обманывают :)
Правы те, кто говорит, что надо учитывать сходимость ряда и область его сходимости.
Пока мы работаем просто со степенными рядами, то это, конечно, неважно. Но если мы захотим перейти от бесконечного числа коэффициентов к представлению в виде формулы, и получить производящую функцию, то нам придётся идти на поклон к ТФКП, и просить у них функцию, ряд Тейлора которой имеет те же коэффициенты, что и наш степенной ряд. Только после этого у нас появится круг сходимости, в котором мы сможем манипулировать нашими рядами как функциями. А если вдруг нам попадётся ряд sum(x^n*n!) — чем нам вообще может помочь метод производящих функций? Конечно, в каких-нибудь p-адических числах этот ряд к чему-то сходится, только вот к чему?
Пока мы работаем просто со степенными рядами, то это, конечно, неважно. Но если мы захотим перейти от бесконечного числа коэффициентов к представлению в виде формулы, и получить производящую функцию, то нам придётся идти на поклон к ТФКП, и просить у них функцию, ряд Тейлора которой имеет те же коэффициенты, что и наш степенной ряд. Только после этого у нас появится круг сходимости, в котором мы сможем манипулировать нашими рядами как функциями. А если вдруг нам попадётся ряд sum(x^n*n!) — чем нам вообще может помочь метод производящих функций? Конечно, в каких-нибудь p-адических числах этот ряд к чему-то сходится, только вот к чему?
Я только начал читать, но возник вопрос:
А как работает формула про (a+b)^n при отсутствии коммутативности?
А как работает формула про (a+b)^n при отсутствии коммутативности?
Довольно просто. Берутся все строки длиной n, составленные из a и b (их всего 2^n), для каждой вычисляется произведение, а потом эти произведения складываются.
Это в предположении, что некоммутативно только умножение (в кольцах сложение коммутативно всегда).
Это в предположении, что некоммутативно только умножение (в кольцах сложение коммутативно всегда).
(a+b)^2 = a*a + a*b + b*a + b*b. Откуда тут получится 2*a*b?
Ниоткуда не получится. Будет сумма 4=2^2 произведений, как у вас и написано.
А (a+b)^3 = a^3 + a^2*b + a*b*a + a*b^2 + b*a^2 + b*a*b + b^2*a + b^3, сумма 8 произведений. Всё, как и должно быть.
Возможно, я неправильно понял вопрос. «Как работает формула» я прочитал, как «какая получается формула». А классический бином Ньютона, конечно, работать не будет.
А (a+b)^3 = a^3 + a^2*b + a*b*a + a*b^2 + b*a^2 + b*a*b + b^2*a + b^3, сумма 8 произведений. Всё, как и должно быть.
Возможно, я неправильно понял вопрос. «Как работает формула» я прочитал, как «какая получается формула». А классический бином Ньютона, конечно, работать не будет.
Почему сворачивая цепочку (1-z^2)(1+z^2)(1+z^4)… мы получим единицу? Если z — это нечто «формальное», то как оно может иметь какой-то предел вообще?
Кто-нибудь покажет на практике вычисление конкретного вида полного полинома Белла?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Производящие функции — туда и обратно