განმეორებითი მეთოდები. განმეორებითი მიმართებების ზოგადი და კონკრეტული ამონახსნები გამოთვალეთ n რიგის დეტერმინანტები განმეორებითი მიმართებების მეთოდით

დიდი რაოდენობით დაკვირვების მონაცემებით Xალბათობის განტოლების გადაჭრის სასრული მეთოდები იწვევს მნიშვნელოვან გამოთვლით სირთულეებს, რომლებიც დაკავშირებულია დიდი რაოდენობის საწყისი მონაცემების დამახსოვრებასთან და გამოთვლების შუალედურ შედეგებთან. ამ მხრივ განსაკუთრებული ინტერესია განმეორებადი მეთოდები, რომლებშიც მაქსიმალური ალბათობის შეფასება ეტაპობრივად გამოითვლება თანდათან მზარდი სიზუსტით, ყოველი ნაბიჯი დაკავშირებულია ახალი დაკვირვების მონაცემების მიღებასთან და განმეორებითი პროცედურა აგებულია ისე, რომ ინახება დაიმახსოვრე რაც შეიძლება ნაკლები მონაცემები წინადან.ნაბიჯები. დამატებითი და ძალიან მნიშვნელოვანი უპირატესობა რეკურსიული მეთოდების პრაქტიკული თვალსაზრისით არის მზადყოფნა გამოსცეს შედეგი ნებისმიერ შუალედურ საფეხურზე.

ეს მიზანშეწონილს ხდის განმეორებადი მეთოდების გამოყენებას იმ შემთხვევებშიც კი, როდესაც შესაძლებელია მაქსიმალური ალბათობის განტოლების ზუსტი ამონახსნის მიღება სასრული მეთოდით და კიდევ უფრო ღირებულს ხდის მათ, როდესაც შეუძლებელია ზუსტი ანალიტიკური გამოხატვის პოვნა მაქსიმუმის შესაფასებლად. ალბათობა.

დაე, დაკვირვების მონაცემების სიმრავლე იყოს თანმიმდევრობა, რომლის აღწერისთვისაც შემოგვაქვს ვექტორი. (როგორც ყოველთვის, მისი თითოეული კომპონენტი, თავის მხრივ, შეიძლება იყოს ვექტორი, შემთხვევითი პროცესის სეგმენტი და ა.შ.). მოდით იყოს ალბათობის ფუნქცია და

მისი ლოგარითმი. ეს უკანასკნელი ყოველთვის შეიძლება წარმოდგენილი იყოს როგორც

დაკვირვების მონაცემთა ნაკრების ჟურნალის ალბათობა ბოლო მნიშვნელობის გარეშე და

მნიშვნელობის პირობითი ალბათობის სიმკვრივის ლოგარითმი მოცემული მნიშვნელობებისთვის და.

ალბათობის ფუნქციის ლოგარითმისთვის წარმოდგენა (7.5.16) არის მაქსიმალური ალბათობის შეფასების გამოთვლის განმეორებითი პროცედურის მიღების საფუძველი. განვიხილოთ ჩვეულებრივი შემთხვევა. ამ შემთხვევაში მაქსიმალური ალბათობის შეფასება შეიძლება მოიძებნოს განტოლების ამოხსნის სახით

რომელიც (7.1.6)-სგან განსხვავდება მხოლოდ ინდექსის შემოღებით p yალბათობის ფუნქციის ლოგარითმი.

მოდით აღვნიშნოთ ამ განტოლების ამონახსნი, რითაც ხაზგასმით აღვნიშნავთ, რომ ეს შეფასება მიღებული იქნა დაკვირვების მონაცემების მთლიანობიდან. ანალოგიურად, განტოლების ამოხსნით აღვნიშნოთ მონაცემთა სიმრავლიდან მიღებული მაქსიმალური ალბათობის შეფასება.

განტოლება (7.5.19) შეიძლება გადაიწეროს (7.5.16) შემდეგი ფორმით:

მოდით გავაფართოვოთ (7.5.20)-ის მარცხენა მხარე ტეილორის სერიაში წერტილის სიახლოვეს. სადაც

(7.5.22)

ფუნქციის გრადიენტის ვექტორი წერტილში; ტერმინი ქრება იმის გამო, რომ , არის ალბათობის განტოლების ამოხსნა წინა (P - 1) ნაბიჯი:

ალბათობის ფუნქციის ლოგარითმის მეორე წარმოებულების სიმეტრიულ მატრიცას წერტილში, საპირისპირო ნიშნით აღებული, გაფართოების დაუწერელ ტერმინებს აქვთ სიმცირის კვადრატული და უმაღლესი რიგი სხვაობის მიმართ. ამ უკანასკნელის უგულებელყოფით, ჩვენ ვიღებთ მაქსიმალური ალბათობის განტოლების შემდეგ სავარაუდო ამონახსანს:

სად არის შებრუნებული მატრიცა.

ეს გამოსავალი წარმოდგენილია განმეორებითი მიმართების სახით, რომელიც განსაზღვრავს შეფასების შემდეგ მნიშვნელობას წინა საფეხურის შეფასებისა და კორექტირების გზით. , დამოკიდებულია ხელმისაწვდომ დაკვირვების მონაცემებზე პირდაპირ და წინა შეფასებით. კორექტირება ყალიბდება როგორც ახლად მიღებული სიდიდის პირობითი ალბათობის სიმკვრივის ლოგარითმის გრადიენტის ნამრავლი. X n წინა შეფასების ტოლ წერტილში, წონის მატრიცაზე . ეს უკანასკნელი განისაზღვრება გამოხატულებით (7.5.23) და ასევე დამოკიდებულია წინა საფეხურზე არსებულ შეფასებაზე და მისი დამოკიდებულება ახალ დაკვირვების მონაცემებზე მთლიანად განისაზღვრება პირობითი ალბათობის სიმკვრივის ლოგარითმის ფორმით.

მიმართების ფორმა (7.5.24) ძალიან ჰგავს (7.5.8), რომელიც ახორციელებს ნიუტონის მეთოდით მაქსიმალური ალბათობის შეფასების გამოთვლის განმეორებით ხერხს. თუმცა, ფაქტობრივად, ისინი მნიშვნელოვნად განსხვავდებიან ერთმანეთისგან. (7.5.8) შეფასების წინა მნიშვნელობის კორექტირება განისაზღვრება მთლიანი ალბათობის ფუნქციის ლოგარითმის გრადიენტის სიდიდით, რომელიც ყოველთვის დამოკიდებულია ყველა არსებულ დაკვირვების მონაცემზე, რაც მოითხოვს მთელი პოპულაციის დამახსოვრებას. (7.5.24) შესაბამისად, კორექტირება განისაზღვრება გრადიენტის სიდიდით, რომელიც, პირობითი ალბათობის სიმკვრივის თვისებების გამო, ფაქტობრივად დამოკიდებულია მხოლოდ იმ მნიშვნელობებზე () რომლებიც ძლიერ სტატისტიკურ კავშირშია. თან Xნ. ეს განსხვავება არის წინა მიახლოების განსაკუთრებული არჩევანის შედეგი, როგორც მაქსიმალური ალბათობის შეფასება, რომელიც ნაპოვნია დაკვირვების მონაცემების ნაკრებიდან, შემცირებული ერთი მნიშვნელობით, და განსაკუთრებით გამოხატულია () დამოუკიდებელი მნიშვნელობებისთვის. ამ უკანასკნელ შემთხვევაში

რის გამოც იგი დამოკიდებულია მხოლოდ და X n და გრადიენტი არის მხოლოდ შეფასების წინა მნიშვნელობიდან და ახლად მიღებული P-სათვალთვალო მონაცემების ნაბიჯი. ამიტომ, დამოუკიდებელი მნიშვნელობებისთვის, ვექტორის ფორმირებისთვის, არ არის საჭირო წინა საფეხურიდან სხვა ინფორმაციის შენახვა, გარდა შეფასების მნიშვნელობისა.

ანალოგიურად, დაკვირვების მონაცემების მარკოვის თანმიმდევრობის შემთხვევაში, ანუ როდის

ვექტორი დამოკიდებულია მხოლოდ მიმდინარე და ერთ წინა მნიშვნელობაზე. ამ შემთხვევაში, გაანგარიშებისთვის საჭიროა წინა საფეხურიდან, მნიშვნელობის გარდა, დაიმახსოვროთ მხოლოდ მნიშვნელობა, მაგრამ არა დაკვირვების მონაცემების მთელი ნაკრები, როგორც განმეორებით პროცედურაში. ზოგადად, გაანგარიშებამ შეიძლება მოითხოვოს წინა მნიშვნელობების უფრო დიდი რაოდენობის შენახვა (), თუმცა, მხოლოდ იმ მნიშვნელობების გათვალისწინების აუცილებლობის გამო, რომლებიც სტატისტიკურად არის დამოკიდებული, ეს რიცხვი თითქმის ყოველთვის ნაკლებია. დაკვირვების მონაცემთა ნაკრების მთლიანი მოცულობა. ასე რომ, თუ ვექტორი აღწერს დროის მიმდევრობას, მაშინ ამ მიმდევრობის დასამახსოვრებელი წევრების რაოდენობა განისაზღვრება მისი კორელაციის დროით და მათი ფარდობითი წილი მცირდება უკუპროპორციულად. ნროგორც დამოუკიდებელი ღირებულებების შემთხვევაში.

ახლა განვიხილოთ წონის მატრიცის სტრუქტურა, რომელიც შედის რეკურენტულ მიმართებაში (7.5.24). განმარტების მიხედვით (7.5.23), ტერმინის არსებობის გამო, ის ზოგადად დამოკიდებულია ყველა მნიშვნელობაზე, თუნდაც დამოუკიდებელ მნიშვნელობებზე, რაც ართმევს განმეორებით კავშირს (7.5.24) უპირატესობებთან დაკავშირებულ წინა ნაბიჯიდან შენახული მონაცემების შესაძლო შემცირება. მატრიცის მიახლოების რამდენიმე გზა არსებობს , რომლებიც ასწორებენ ამ ნაკლს.

პირველი მათგანი დაფუძნებულია შეფასების ორ თანმიმდევრულ მნიშვნელობას შორის მცირე სხვაობის ძირითადი დაშვების უფრო თანმიმდევრულ გამოყენებაზე, რომელიც არის განმეორებითი ურთიერთობის მიღების საფუძველი (7.5.24). ეს საშუალებას გვაძლევს მივიღოთ მსგავსი რეციდივის მიმართება წონის მატრიცისთვის. მართლაც, სიმცირის გამოყენებით (7.5.23), გვაქვს

აღნიშვნის შემოღებით

(7.5.24) და (7.5.25)-დან ვიღებთ ვექტორისა და წონის მატრიცის განმეორებადი მიმართებების სისტემას

ეს სისტემა, საწყის მნიშვნელობებთან ერთად, მთლიანად განსაზღვრავს შეფასების მნიშვნელობას ნებისმიერ საფეხურზე, მოითხოვს თითოეულ მათგანს გამოთვალოს მხოლოდ გრადიენტი და პირობითი ალბათობის სიმკვრივის ლოგარითმის მეორე წარმოებულების მატრიცა მიმდინარე დაკვირვებული მნიშვნელობისთვის. საწყისი მნიშვნელობები არჩეულია ხელმისაწვდომი აპრიორული მონაცემების გათვალისწინებით შესაძლო მნიშვნელობებზე და პარამეტრების ცვლილების დიაპაზონზე, ხოლო ამ მონაცემების არარსებობის შემთხვევაში, ისინი მიიღება ნულად (,).

დამოუკიდებელი მნიშვნელობებისთვის, განმეორებითი ურთიერთობების სისტემა (7.5.27) აშკარად აღწერს მრავალგანზომილებიან (განზომილებებს) მარკოვის შემთხვევით პროცესს, რომლის კომპონენტი კონვერგირდება პარამეტრის ნამდვილ მნიშვნელობასთან, ხოლო კომპონენტი კონვერგირდება ფიშერის ინფორმაციის მატრიცასთან (7.3. 8), სადაც არის სავარაუდო პარამეტრის ჭეშმარიტი მნიშვნელობა და იზრდება განუსაზღვრელი ვადით პ.სისტემას (7.5.27) აქვს მსგავსი კონვერგენციის თვისებები უფრო ზოგად პირობებში, თუ თანმიმდევრობა ერგოდიულია.

აღნიშნული მეთოდებიდან მეორე ეფუძნება ალბათობის ფუნქციის ლოგარითმის მეორე წარმოებულების მატრიცის შეცვლას თავისი მათემატიკური მოლოდინით - ფიშერის ინფორმაციის მატრიცით, რომელიც, (7.5.16) გათვალისწინებით, შეიძლება დაიწეროს როგორც:

სადაც ანალოგიურად (7.5.26)

(7.5.24) მატრიცის ჩანაცვლებით მატრიცით, მივიღებთ განმეორებადი მიმართებას.

საკრისონის მიერ შემოთავაზებული მაქსიმალური ალბათობის შეფასებების მიახლოებითი გამოთვლისთვის (დედანში დამოუკიდებელი იდენტურად განაწილებული, როდესაც და . ეს განმეორებითი მიმართება უფრო მარტივია ვიდრე სისტემა (7.5.27), ვინაიდან ოპტიმალური წონის მატრიცა ჩანაცვლებულია მისი მათემატიკურით. მოლოდინი და ხელმისაწვდომი დაკვირვების მონაცემები არ არის საჭირო მის საპოვნელად, გარდა იმ შემთხვევებისა, რომლებიც კონცენტრირებულია შეფასების ღირებულებაში. ამავდროულად, აშკარაა, რომ ასეთი ჩანაცვლება ნიშნავს დამატებითი მოთხოვნის შესრულების აუცილებლობას (7.5. 27) რომ მეორე წარმოებულების მატრიცა ახლოს იყოს მის მათემატიკურ მოლოდინთან.

თუ ალბათობის სიმკვრივის განაწილება და მატრიცა იცვლება საფეხურიდან საფეხურზე, თითოეული საფეხურის პირდაპირ პოვნა შეიძლება მოითხოვდეს ძალიან ბევრ გამოთვლას. ამავდროულად, შედეგების სიზუსტის დამატებითი შემცირების გამო, რომელიც განისაზღვრება მცირე განსხვავებების ნულის უტოლობით, შეიძლება გააგრძელოთ მატრიცის სავარაუდო მნიშვნელობის განმეორებითი გამოთვლა. ამ სავარაუდო მნიშვნელობის წინა აღნიშვნას რომ დავუბრუნდეთ, ჩვენ ვიღებთ განმეორებითი ურთიერთობების სხვა სისტემას

მატრიცის მათემატიკური მოლოდინი (ფიშერის ინფორმაციის მატრიცა ერთი დაკვირვებისთვის), აღებული პუნქტში. ეს სისტემა განსხვავდება (7.5.27)-სგან იმით, რომ განმეორებითი ურთიერთობებიდან მეორე (7.5.31) პირდაპირ არ მოიცავს დაკვირვების მონაცემებს.

ზემოთ განხილული რეციდივის მიმართებების ნებისმიერი სისტემა სავსებით ზუსტია, თუ ფუნქცია კვადრატულად არის დამოკიდებული და დამატებით მეორე წარმოებულების მატრიცა არ არის დამოკიდებული. სინამდვილეში, ეს შეესაბამება დამოუკიდებელი ნორმალურად განაწილებული (არა აუცილებლად თანაბრად) მნიშვნელობების შემთხვევას უცნობი მათემატიკური მოლოდინით, რაც არის სავარაუდო პარამეტრი.

განმეორებითი ურთიერთობების სისტემა (7.5.24) იძლევა მაქსიმალური ალბათობის განტოლების ზუსტ ამოხსნას ბევრად უფრო ფართო პირობებში, ერთადერთი მოთხოვნით, რომ ფუნქცია კვადრატულად იყოს დამოკიდებული . დამოკიდებულება თვითნებურია, რაც შეესაბამება პოპულაციის ალბათობის განაწილების ფართო კლასს, როგორც დამოუკიდებელი, ისე დამოკიდებული მნიშვნელობებით.

განხილულ ზოგად მეთოდებთან ერთად, არსებობს რამდენიმე მეთოდი წონის კოეფიციენტების მატრიცის არჩევისთვის რეციდივის მიმართებაში (7.5.24), ადაპტირებული გარკვეულ სპეციფიკურ შეზღუდვებზე. მათგან უმარტივესი არის არჩევანი დიაგონალური მატრიცის სახით, ასე რომ, ( მეარის იდენტურობის მატრიცა), სადაც არის რიცხვითი კოეფიციენტების კლებადი თანმიმდევრობა, რომელიც არჩეულია ალბათობის ფუნქციის თვისებების მიუხედავად, ისევე, როგორც რობინს-მონროს სტოქასტური მიახლოების პროცედურაში, რომელიც განხილული იქნება შემდეგ თავებში.

უნდა აღინიშნოს, რომ ნებისმიერი განმეორებითი ან განმეორებადი პროცედურა მაქსიმალური ალბათობის შეფასების მოსაძებნად, ზოგადად, მიახლოებითია. ამიტომ, ზოგადად რომ ვთქვათ, ამ პროცედურების გამოყენების შედეგად მიღებული შეფასებებისთვის ხელახლა უნდა დადასტურდეს თანმიმდევრულობა, ასიმპტომური ეფექტურობა და ასიმპტომური ნორმალურობა. განმეორებითი პროცედურებისთვის, შეფასებების აუცილებელი თვისებები გარანტირებულია იმით, რომ პრინციპში, ასეთი პროცედურები, გამეორებების შესაბამისი რაოდენობით, წინასწარ განსაზღვრული სიზუსტით ხსნის ალბათობის განტოლებას. განმეორებადი პროცედურებისთვის, როგორიცაა (7.5.27), (7.5.30), (7.5.31) და სხვა, არსებობს სპეციალური მტკიცებულებები. ამავდროულად, რეგულარულობის მოთხოვნის გარდა, დაწესებულია რამდენიმე დამატებითი მოთხოვნა:

ფუნქციის (7.2.2) ქცევის შესახებ ||-ის სხვადასხვა მნიშვნელობებისთვის, განმეორებითი პროცედურის გამოყენებით ამ ფუნქციის გლობალური მაქსიმუმის მისაღწევად პარამეტრის ნამდვილ მნიშვნელობასთან შესაბამის წერტილში;

ალბათობის ფუნქციის ლოგარითმის წარმოებულების მეორე მომენტების ზრდის ბრძანებით დიდი მოდულის მნიშვნელობებისთვის. ეს მოთხოვნები არის უფრო ზოგადი პირობების შედეგი მარკოვის შემთხვევითი პროცესის კომპონენტების ყველა ან ნაწილის დაახლოების წერტილამდე, რომელსაც მივყავართ ამა თუ იმ განმეორებით პროცედურამდე.

დასასრულს, ჩვენ ასევე აღვნიშნავთ, რომ იმ შემთხვევაში, როდესაც არსებობს მაქსიმალური ალბათობის განტოლების ზუსტი ამოხსნა, ის თითქმის ყოველთვის შეიძლება იყოს წარმოდგენილი რეკურსიული ფორმით. ჩვენ ვაძლევთ ორ მარტივ ჰეტეროგენულ მაგალითს. ამრიგად, ნორმალური შემთხვევითი ცვლადის უცნობი მათემატიკური მოლოდინის ელემენტარული შეფასება აგრეგატში ნმისი ნიმუშის მნიშვნელობები საშუალო არითმეტიკული სახით

არის მაქსიმალური ალბათობის შეფასება და შეიძლება წარმოდგენილი იყოს რეკურსიული ფორმით:

რომელიც არის უმარტივესი სპეციალური შემთხვევა (7.5.30).

კიდევ ერთი მაგალითია არარეგულარული მაქსიმალური ალბათობის შეფასება პარამეტრისთვის - მართკუთხა განაწილების სიგანე - დან (7.4.2), რომელიც ასევე შეიძლება განისაზღვროს რეციდივის მიმართებით.

საწყისი მდგომარეობით. ეს განმეორებითი მიმართება სხვა ტიპისაა: მისი მარჯვენა მხარე არ შეიძლება წარმოდგენილი იყოს როგორც წინა შეფასების ჯამი და მცირე კორექტირება, რაც ამ მაგალითის არარეგულარულობის შედეგია; თუმცა, მას აქვს რეკურსიული მიდგომის ყველა უპირატესობა: მას სჭირდება მხოლოდ ერთი რიცხვის დამახსოვრება წინა საფეხურიდან - შეფასებით - და ის მკვეთრად ამცირებს ჩამოთვლას ერთ შედარებამდე, ყველა მნიშვნელობის შედარების ნაცვლად.

მოცემული მაგალითები ასახავს რეკურსიული მეთოდების უპირატესობას იმ შემთხვევაშიც კი, როდესაც მაქსიმალური ალბათობის განტოლება იძლევა ზუსტ ამოხსნას, რადგან შედეგის ანალიტიკური წარმოდგენის სიმარტივე არ არის მისი მოპოვების გამოთვლითი სიმარტივის იდენტური.

7.5.3. გადასვლა უწყვეტ დროზე. დიფერენციალური განტოლებები მაქსიმალური ალბათობის შეფასებისთვის

ახლა განვიხილოთ სპეციალური შემთხვევა, როდესაც ხელმისაწვდომია დაკვირვების მონაცემები Xარ არის აღწერილი ნიმუშის ქულების ნაკრებით , მაგრამ წარმოადგენს ზოგიერთი პროცესის განხორციელების სეგმენტს , ინტერვალზე მოცემული პარამეტრების მიხედვით , უფრო მეტიც, ამ ინტერვალის ხანგრძლივობა შეიძლება გაიზარდოს დაკვირვების დროს (დრო ტცვლადია).

დაკვირვების მონაცემების სტატისტიკური აღწერისთვის, ამ შემთხვევაში, დანერგილია ალბათობის თანაფარდობა ფუნქციონალური, რომელიც არის მნიშვნელობების სიმრავლის ალბათობის სიმკვრივის შეფარდების ზღვარი, მაქსიმუმ, თვითნებურად მოცემულ მნიშვნელობაზე მსგავს ალბათობასთან. სიმკვრივე ზოგიერთ ფიქსირებულ მნიშვნელობაზე და ზოგიერთ შემთხვევაში, როდესაც ის აღიარებს წარმოდგენას, სადაც არის შემთხვევითი პროცესი, დამოუკიდებელი მნიშვნელობების სიმრავლის ალბათობის სიმკვრივეზე, იმ პირობით, რომ. ალბათობის თანაფარდობის ფუნქციონალური გამოყენება შესაძლებელს ხდის აღმოფხვრას ფორმალური სირთულეები ალბათობის სიმკვრივის განსაზღვრისას, რომლებიც წარმოიქმნება უწყვეტ დროზე გადასვლისას.

ალბათობის თანაფარდობის ფუნქციური ლოგარითმი შეიძლება წარმოდგენილი იყოს როგორც

სად არის გარკვეული პროცესი ფუნქციონალური ინტერვალზე. ზოგიერთ შემთხვევაში, ფუნქციური გადაგვარდება ფუნქციად, რომელიც დამოკიდებულია მხოლოდ მნიშვნელობაზე. ასე რომ, თუ

სადაც არის დროისა და პარამეტრების ცნობილი ფუნქცია და არის დელტაკორელირებული შემთხვევითი პროცესი („თეთრი“ ხმაური) სპექტრული სიმკვრივით ნ o, მაშინ, მნიშვნელად ვირჩევთ ალბათობის განაწილების ალბათობის თანაფარდობას Xზე, გვექნება

მოდით - პარამეტრის მაქსიმალური ალბათობის შეფასება, რომელიც აგებულია პროცესის განხორციელებაზე ინტერვალზე, ანუ მაქსიმალური ალბათობის განტოლების ამოხსნა.

ამ განტოლების მარცხენა მხარის დიფერენცირება დროის მიხედვით, მივიღებთ

აღნიშვნის გაცნობა

და განტოლების (7.5.42) ამოხსნით , ჩვენ ვიღებთ დიფერენციალურ განტოლებას მაქსიმალური ალბათობის შეფასებისთვის

მატრიცა, თავის მხრივ, (7.5.37) მიხედვით განისაზღვრება დიფერენციალური განტოლებით

ისევე, როგორც დისკრეტულ შემთხვევაში, მატრიცა (7.5.45), (7.5.47) შეიძლება შეიცვალოს მისი მათემატიკური მოლოდინით - ფიშერის ინფორმაციის მატრიცა მნიშვნელობით და დიფერენციალური განტოლება (7.5.46) წონის მატრიცისთვის. - განტოლებით

სადაც, დისკრეტული შემთხვევის მსგავსად

მეორე წარმოებულების მატრიცის მათემატიკური მოლოდინი.

დიფერენციალური განტოლებათა სიმრავლე (7.5.45), (7.5.46) ან (7.5.45), (7.5.48), საწყის პირობებთან ერთად, რომელთა არჩევასთან დაკავშირებით ყველაფერი ნათქვამია დისკრეტული შემთხვევისთვის, რჩება ძალაში, სრულად. განსაზღვრავს მაქსიმალური ალბათობის შეფასებას დროის ნებისმიერი მომენტისთვის. ამ ნაკრების მოდელირება შესაძლებელია შესაბამისი, ზოგადად რომ ვთქვათ, არაწრფივი ანალოგური მოწყობილობების გამოყენებით ან, შესაბამისი დროის შერჩევით, გადაჭრა კომპიუტერის გამოყენებით. დასასრულს, ჩვენ აღვნიშნავთ ამ განტოლებების ერთ-ერთ მოდიფიკაციას, რაც შესაძლებელს ხდის თავიდან აიცილოთ მატრიცის ინვერსიის საჭიროება.

აღნიშვნის გაცნობა

, სადაც მე

და დროის მიხედვით ურთიერთობის დიფერენცირება , სადაც მეარის იდენტურობის მატრიცა, ჩვენ ვიღებთ (7.5.46) დიფერენციალურ განტოლებას, რომელიც პირდაპირ განსაზღვრავს მატრიცას:

(და ანალოგიურად როცა ჩანაცვლებულია )-ით, რომელიც განტოლებასთან ერთად (7.5.45)

ქულას განსაზღვრავს , მატრიცის ინვერსიის მოთხოვნის გარეშე. ამ შემთხვევაში ხდება გადასვლა უმარტივესი წრფივი დიფერენციალური განტოლებიდან (7.5.46) არაწრფივზე რიკატის ტიპის დიფერენციალურ განტოლებაზე (7.5.51).

კომბინაციური გამოთვლები სასრულ სიმრავლეებზე

შესავალი კომბინატორიკაში

კომბინატორიული ალგორითმების თეორიის საგანი, რომელსაც ხშირად კომბინატორულ გამოთვლებს უწოდებენ, არის გამოთვლები დისკრეტულ მათემატიკური სტრუქტურებზე. ამ თეორიაში დიდი ყურადღება ეთმობა დისკრეტული მათემატიკის ამოცანების გადაჭრის ალგორითმულ მიდგომას, ვარიანტების ჩამოთვლის ოპტიმიზაციას და განხილული გადაწყვეტილებების რაოდენობის შემცირებას.

კომბინატორიული ალგორითმების ველი მოიცავს ამოცანებს, რომლებიც საჭიროებენ სასრულ სიმრავლეში ელემენტების რაოდენობის დათვლას (შეფასებას) ან ამ ელემენტების სპეციალური თანმიმდევრობით ჩამოთვლას (დანართი B). ამ შემთხვევაში ფართოდ გამოიყენება დაბრუნებით ელემენტების შერჩევის პროცედურა და მისი ვარიანტები.

არსებობს ორი სახის დათვლის პრობლემა. მარტივ შემთხვევაში მოცემულია კონკრეტული ნაკრები და ეს საჭიროა განსაზღვრეთ ელემენტების ზუსტი რაოდენობამასში. ზოგად შემთხვევაში, არსებობს გარკვეული პარამეტრით განსაზღვრული კომპლექტების ოჯახი და ნაკრების კარდინალურობა განისაზღვრება პარამეტრის ფუნქციით. ამავე დროს, ხშირია ფუნქციის რიგის საკმარისი შეფასებადა ზოგჯერ მხოლოდ გჭირდებათ მისი ზრდის ტემპის შეფასება. მაგალითად, თუ განსახილველი ნაკრების სიმძლავრე იზრდება ექსპონენტურად ზოგიერთ პარამეტრში, მაშინ ეს შეიძლება იყოს საკმარისი იმისათვის, რომ უარი თქვან პრობლემის შესწავლის შემოთავაზებულ მიდგომაზე, სხვადასხვა დეტალებში შესვლის გარეშე. ამ უფრო ზოგადი ტიპის პრობლემისთვის გამოიყენება ასიმპტომური გაფართოებების, განმეორებითი ურთიერთობებისა და გენერირების ფუნქციების პროცედურები.

ასიმპტომური

ასიმპტოტი არის სპეციალური ხაზი (ყველაზე ხშირად სწორი ხაზი), რომელიც არის განსახილველი მრუდის ზღვარი.

ასიმპტოტიკა არის ფუნქციების ზრდის ტემპების შეფასების და შედარების ხელოვნება. ამბობენ, რომ ზე X®¥ ფუნქცია "იქცევა ისე X", ან "იზრდება იმავე ტემპით, როგორც X“ და ზე X®0 "იქცევა ისე, როგორც 1/ x". ამბობენ, რომ "ლოგი xზე x®0 და ნებისმიერი e>0 იქცევა ისე xე და რა ნ®¥ იზრდება არა უფრო სწრაფად, ვიდრე ნჟურნალი ნასეთი არაზუსტი, მაგრამ ინტუიციურად მკაფიო განცხადებები სასარგებლოა ფუნქციების შედარებისას ისევე, როგორც ურთიერთობები.<, £ и = при сравнивании чисел.

მოდით განვსაზღვროთ სამი ძირითადი ასიმპტომური ურთიერთობა.

განმარტება 1.ფუნქცია ვ(x) უდრის გ(x) ზე X® x0, თუ და მხოლოდ თუ =1.

ამ შემთხვევაში, ფუნქცია ითვლება ვ(x) უსიმპტომოდ უდრის ფუნქციას გ(x) ან რა ვ(x) იზრდება იმავე ტემპით, როგორც გ(x).

განმარტება 2. ვ(x)=o( გ(x)) ზე x® x0, თუ და მხოლოდ თუ =0.

ამბობენ, რომ ზე x® x 0 ვ(x) უფრო ნელა იზრდება ვიდრე გ(x), ან რა ვ(x) "არსებობს ო-პატარა"-დან გ(x).

განმარტება 3 . ვ(x)=ო( გ(x)) ზე x® x0, თუ და მხოლოდ იმ შემთხვევაში, თუ არსებობს მუდმივი C ისეთი, რომ sup =C.

ამ შემთხვევაში ასე ამბობენ ვ(x) იზრდება არა უფრო სწრაფად, ვიდრე გ(x), ან სხვა x® x 0 ვ(x) "არსებობს დიდი ო"-დან გ(x).

თანაფარდობა ვ(x)=გ(x)+ო(თ(x)) ზე x®¥ ნიშნავს იმას ვ(x)-გ(x)=ო(თ(x)). ანალოგიურად ვ(x)=გ(x)+შესახებ(თ(x)) ნიშნავს რომ ვ(x)-გ(x)=ო(თ(x)).

გამოთქმები O( ) და o( ) ასევე შეიძლება გამოვიყენოთ უტოლობაში. მაგალითად, უთანასწორობა x+ო(x) £ 2 xზე x®0 ნიშნავს, რომ ნებისმიერი ფუნქციისთვის ვ(x) ისეთივე როგორც ვ(x)=ო(x), ზე x®¥ x+f(x) £ 2 xყველა საკმარისად დიდი მნიშვნელობისთვის X.

მოდით წარმოვადგინოთ რამდენიმე სასარგებლო ასიმპტოტური თანასწორობა.

მრავალწევრი ასიმპტომურად უდრის მის უმაღლეს წევრს:

ზე x®¥; (4.1)

ზე x®¥; (4.2)

ზე x®¥ და კ¹0. (4.3)

მთელი რიცხვების ძალაუფლების ჯამი აკმაყოფილებს მიმართებას:

ზე ნ®¥. (4.4)

აქედან გამომდინარე, კერძოდ, გვაქვს ნ®¥

უფრო ზოგად შემთხვევაში, როცა ნ®¥ და ნებისმიერი მთელი რიცხვისთვის კ³0

; (4.6)

. (4.7)

განმეორებადი ურთიერთობები

მოდით, ილუსტრირებათ განმეორებითი ურთიერთობების კონცეფცია კლასიკურ პრობლემასთან, რომელიც დასვა და შეისწავლა ფიბონაჩის მიერ დაახლოებით 1200 წელს.

ფიბონაჩის პრობლემა წამოაყენა მოთხრობის სახით კურდღლების პოპულაციის ზრდის ტემპის შესახებ შემდეგი ვარაუდებით. ყველაფერი იწყება ერთი წყვილი კურდღლით. კურდღლის თითოეული წყვილი ხდება ნაყოფიერი (განაყოფიერებული) ერთი თვის შემდეგ, რის შემდეგაც ყოველი წყვილი ყოველთვიურად შობს კურდღლის ახალ წყვილს. კურდღლები არასოდეს კვდებიან და მათი გამრავლება არასოდეს ჩერდება. დაე იყოს F n- კურდღლების წყვილი რაოდენობა პოპულაციაში შემდეგ ნთვეები და ეს მოსახლეობა შედგებოდეს N nნაგვის წყვილები და O n"ძველი" წყვილი, ე.ი. F n = N n + O n. ამრიგად, მომდევნო თვეში შემდეგი მოვლენები მოხდება:

ძველი მოსახლეობა ( ნ+1)-ე მომენტი გაიზრდება იმ დროს დაბადებულთა რაოდენობით ნ, ე.ი. O n+1 = O n + N n= F n;

ყველა მოხუცი დროის გარკვეულ მომენტში ნწყვილი აწარმოებს დროს ( ნ+1) რამდენიმე შთამომავალი, ე.ი. Nn+1= C n.

მომდევნო თვეში ეს ნიმუში მეორდება:

O n+2 = O n+1+ Nn+1= Fn+1,

Nn+2=O n+1;

ამ თანასწორობების კომბინაციით, მივიღებთ ფიბონაჩის განმეორების მიმართებას:

O n+2 + Nn+2=Fn+1 + O n+1,

Fn+2 = Fn+1 + F n. (4.8)

ფიბონაჩის მიმდევრობის საწყისი პირობების არჩევანი არ არის მნიშვნელოვანი; ამ თანმიმდევრობის არსებითი თვისებები განისაზღვრება განმეორებადი მიმართებით (4.8). ჩვეულებრივ სჯეროდა F0=0, F1= 1 (ზოგჯერ F0=F1=1).

რეციდივის მიმართება (4.8) არის ერთგვაროვანი წრფივი რეციდივის მიმართების განსაკუთრებული შემთხვევა მუდმივი კოეფიციენტებით:

x n = a 1 x n-1 + a 2 x n-2 +…a k x n-k, (4.9)

სადაც კოეფიციენტები ა იარ არის დამოკიდებული ნდა x 1, x2, …, x kმიჩნეულად ითვლება.

არსებობს გადაჭრის ზოგადი მეთოდი (ანუ პოვნა x nროგორც ფუნქცია ნ) წრფივი განმეორებადი მიმართებები მუდმივი კოეფიციენტებით. განვიხილოთ ეს მეთოდი მაგალითად (4.8) მიმართებით. გამოსავალს ვპოულობთ ფორმაში

F n=crn (4.10)

მუდმივთან ერთად დანდა რ. ამ გამოთქმის (4.8) ჩანაცვლებით, მივიღებთ

cr + 2 = crn+ 1 + crn,

crn(რნ-რ-1)=0. (4.11)

Ეს ნიშნავს, რომ F n=crnარის გამოსავალი თუ რომელიმე დან=0, ან რ= 0 (და შესაბამისად F n =0 ყველასთვის ნ), და ასევე (და ეს უფრო საინტერესო შემთხვევაა) თუ რ 2 - r -1=0 და მუდმივი დანთვითნებური. შემდეგ (4.11)-დან მოყვება

რ= ან რ = . (4.12)

რიცხვი "1.618" ცნობილია, როგორც "ოქროს" თანაფარდობა, რადგან უძველესი დროიდან ითვლებოდა, რომ სამკუთხედს (მართკუთხედს) გვერდებით 1 აქვს ყველაზე თვალისმომჭრელი პროპორციები.

ერთგვაროვანი წრფივი რეციდივის ორი ამონახსნის ჯამი აშკარად ასევე გამოსავალია და შეიძლება რეალურად აჩვენოთ, რომ ფიბონაჩის მიმდევრობის ზოგადი ამონახსნები არის

F n= , (4.13)

სად არის მუდმივები დანდა საწყისიგანისაზღვრება საწყისი პირობებით. F 0 =0 და F 1 =1 დაყენებით, მივიღებთ წრფივი განტოლებების შემდეგ სისტემას:

, (4.14)

რომლის ხსნარი იძლევა

გ = -გ" = . (4.15)

წრფივი განმეორებადი მიმართებები მუდმივი კოეფიციენტებით. განმეორებითი ურთიერთობების ძირითადი განმარტებები და მაგალითები ხშირად ერთი კომბინატორული ამოცანის ამოხსნა შეიძლება შემცირდეს მცირე განზომილების მსგავსი ამოცანების გადაწყვეტამდე, ზოგიერთი მიმართების დახმარებით, რომელსაც ეწოდება რეციდიცია ლათინური სიტყვიდან recurrere - დაბრუნება. ამრიგად, რთული პრობლემის გადაწყვეტა შეიძლება მიღწეული იყოს უფრო მარტივი პრობლემების გადაწყვეტის თანმიმდევრული მოძიებით და შემდეგ განმეორებითი ურთიერთობების მიხედვით გადაანგარიშებით რთული პრობლემის გადაწყვეტის მოსაძებნად. განმეორებითი კავშირი...

გააზიარეთ სამუშაო სოციალურ ქსელებში

თუ ეს ნამუშევარი არ მოგწონთ, გვერდის ბოლოში არის მსგავსი ნამუშევრების სია. თქვენ ასევე შეგიძლიათ გამოიყენოთ ძებნის ღილაკი

არანოვი ვიქტორ პავლოვიჩი დისკრეტული მათემატიკა. ნაწილი 2. კომბინატორიკის ელემენტები.

ლექცია 5

ლექციები 5. განმეორებითი ურთიერთობების მეთოდი

ლექციის გეგმა:

1. განმეორებითი ურთიერთობების ძირითადი განმარტებები და მაგალითები.
2. წრფივი განმეორებადი მიმართებები მუდმივი კოეფიციენტებით. ფორმულა

ბინე.

1. განმეორებითი ურთიერთობების ძირითადი განმარტებები და მაგალითები

ხშირად ერთი კომბინატორიული ამოცანის ამოხსნა შეიძლება შემცირდეს ქვედა განზომილების მსგავსი ამოცანების გადაწყვეტამდე, ზოგიერთი მიმართების გამოყენებით, რომელსაც ეწოდება მდინარე.რ ქირა (ლათინური სიტყვიდანგანმეორებადი - დაბრუნების). ამრიგად, რთული პრობლემის გადაწყვეტა შეიძლება მიღებულ იქნეს მარტივი პრობლემების გადაწყვეტის თანმიმდევრული მოძიებით და შემდგომ, ნ.ე განმეორებითი ურთიერთობებით გამოთვლა, რთული პრობლემის გადაწყვეტის პოვნა.

-მე რიგის რეციდივის მიმართებარიცხვთა მიმდევრობის ელემენტებს შორის ფორმის ფორმულა ეწოდება

(1)

პირადი გადაწყვეტილებაგანმეორებითი კავშირი არის ნებისმიერი მემკვიდრებ მიმართება, რომელიც აქცევს მიმართებას (1) იდენტურად. კავშირი (1) imე უსაზღვროდ ბევრი კონკრეტული გამოსავალია, რადგან პირველი ელემენტები თანმიმდევრულიაშესახებ sti შეიძლება დაყენდეს თვითნებურად. მაგალითად, თანმიმდევრობა არის pე განმეორებითი ურთიერთობაშესახებ გადაწყვეტილებები, რადგან იდენტურობა ინარჩუნებს.

-მე-ე რიგის განმეორებითი მიმართების ამოხსნა ეწოდებასაერთო, თუ ეს არის ა დამოკიდებულია თვითნებურ მუდმივებზე და ამ მუდმივების არჩევით შეგვიძლიაკარგად მაგრამ მიიღეთ ამ ურთიერთობის ნებისმიერი გამოსავალი. მაგალითად, კოეფიციენტებისთვისე ნია

(2)

ზოგადი გამოსავალი იქნება

. (3)

მართლაც, ადვილია იმის შემოწმება, რომ მიმდევრობა (3) აქცევს მიმართებას (2) იდენტურად. ამიტომ, საჭიროა მხოლოდ იმის ჩვენება, რომ (2) მიმართების ნებისმიერ ამონახსანს შეუძლიაკარგად მაგრამ წარმოადგენენ (3) სახით. მაგრამ ამ ურთიერთობის ნებისმიერი გამოსავალი ცალსახად არის განსაზღვრული.თ ღირებულებებით და. ამიტომ, უნდა დავამტკიცოთ, რომ ნებისმიერი რიცხვისთვის და არსებობს მმაგრამ რომელი ღირებულებები და რა

ვინაიდან ამ სისტემას აქვს გამოსავალი ნებისმიერი მნიშვნელობისთვის და, მაშინ ამოხსნა (3) ნამდვილად არის მიმართების ზოგადი ამოხსნა (2).

მაგალითი 1. ფიბონაჩის რიცხვები.1202 წელს ცნობილმა იტალიელმა მათემატიკოსმა ლეშესახებ ნარდო პიზადან, რომელიც უფრო ცნობილია თავისი მეტსახელით ფიბონაჩი ( Fib o nacci - შემოკლებით filius Bonacci , ანუ ბონაჩის ძე), დაიწერა წიგნი " Liber abacci "(" წიგნი და ჰა აბაკუსის შესახებ"). ეს წიგნი ჩვენამდე მოვიდა მეორე ვერსიით, რომელიც თარიღდება 1228 წლით. მოდით განვიხილოთ ამ წიგნში მოცემული მრავალი პრობლემადან ერთ-ერთი.

კურდღლის წყვილს თვეში ერთხელ მოაქვს ორი კურდღლის (ქალი და მამრი) შთამომავალი და ა.შ.და ვიდრე ახალშობილ კურდღლებს, დაბადებიდან ორი თვის შემდეგ უკვე შთამომავლობა აქვთ. რამდენი კურდღელი გამოჩნდებაე რეს წელი, თუ წლის დასაწყისში იყო ერთი წყვილი კურდღელი?

პრობლემის მდგომარეობიდან გამომდინარეობს, რომ ერთ თვეში ორი წყვილი კურდღელი იქნება. ორი თვის შემდეგმე მხოლოდ პირველი წყვილი კურდღელი მოგცემთ შთამომავლობას და თქვენ მიიღებთ 3 წყვილს.ა კიდევ ერთ თვეში შთამომავლობას გამოიღებს კურდღლების ორიგინალური წყვილიც და ორი თვის წინ გამოჩენილი კურდღლის წყვილი. შესაბამისად, სულ იქნება 5 წყვილი კურდღელი და ა.შ.

რ-ის დასაწყისიდან თვეების შემდეგ აღნიშნეთ კურდღლების წყვილი რაოდენობაშესახებ დიახ. შემდეგ თვეებში იქნება ეს წყვილი და კიდევ ბევრი ახალშობილი წყვილი.შესახებ სახეები, რამდენი იყო თვის ბოლოს, ანუ მეტი წყვილი. ამრიგად, არსებობს რე მიმდინარე თანაფარდობა

. (4)

ვინაიდან, მაშინ თანმიმდევრულად ვპოულობთ: და ა.შ. ეს რიცხვები ქმნიან მიმდევრობას

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,

დაურეკაფიბონაჩისა და მისი წევრების მახლობლად - ფიბონაჩის რიცხვები. მათ აქვთ მრავალი შესანიშნავი თვისება. ფიბონაჩის რიცხვები დაკავშირებულია შემდეგ კომბინატორთანმაგრამ ეკლიანი ამოცანა.

იპოვეთ სიგრძის ორობითი სიტყვების რაოდენობა, რომლებშიც არ არის ორი 1დ მწკრივი.

მოდით ვუწოდოთ ამ სიტყვებსსწორი და აღნიშნე მათი რიცხვი . მოდით გავყოთ ამ რეგულარული სიტყვების სიმრავლე ორ კლასად: სიტყვები, რომლებიც მთავრდება ნულით და სიტყვები, რომლებიც მთავრდება ერთში. ავღნიშნოთ სიტყვების რაოდენობა ამ კლასებში დათ პასუხისმგებელი. დამატების წესის მიხედვით

(5)

ცხადია, ნულზე დამთავრებული სიტყვისთვის პირველი სიმბოლოები ქმნიან სიგრძის რეგულარულ სიტყვას, ან სხვა სიტყვებით რომ ვთქვათ, არის ბიექცია ნულზე დამთავრებული რეგულარული სიგრძის სიტყვებისა და რეგულარული სიგრძის სიტყვების სიმრავლეს შორის, ანუ.

თუ სწორი სიგრძის სიტყვა მთავრდება ერთით, მაშინ ამ სიტყვის წინა სიმბოლო უნდა იყოს ნული, ხოლო პირველი სიმბოლოები უნდა ქმნიან სწორი სიგრძის სიტყვას. როგორც წინა შემთხვევაში, ჩვენ კვლავ გვაქვს ბიექცია სიგრძის რეგულარული სიტყვების სიმრავლესა და სიგრძის რეგულარული სიტყვების სიმრავლეს შორის. შესაბამისად. . ფორმულიდან (5) ვიღებთ რეკურსიულ მიმართებასშესახებ

. (6)

რეციდივის მიმართების გამოსაყენებლად აუცილებელია ამ გამოთვლადან ყველა წინა მნიშვნელობის შეცვლა. მაგალითად, თუ ჩვენ უნდა ვიცოდეთ წესების რაოდენობაბ 10 სიმბოლოსგან შემდგარი სიტყვები, შემდეგ მისი პოვნა შესაძლებელია შემდეგი ცხრილის თანმიმდევრული შევსებითბ სახე:

ცხრილი 1

პირველი ორი მნიშვნელობა გვხვდება პირდაპირ (-სიტყვები 0 და 1; - სიტყვები 000, 010, 101), ხოლო დანარჩენი - ფორმულით (6).

მაგალითი 2 არაასოციაციური ბინით გამოსახულებაში ფრჩხილების განთავსების პრობლემაოპერაცია. მოდით "" აღნიშნავს ზოგიერთ ორობით ოპერაციას. განიხილეთს გამოთქმა, რომელშიც სიმბოლო აღნიშნავს ორობით არაასოციაციასმაგრამ აქტიური ოპერაცია. ფრჩხილების მოწყობის რამდენი განსხვავებული გზა არსებობს ამაში s raz e nii?

არაასოციაციური ოპერაციის მაგალითია ვექტორული ნამრავლი. კიდევ ერთი მაგალითია კომპიუტერზე შესრულებული ჩვეულებრივი შეკრება და გამრავლება. -თან ერთადდა რომ კომპიუტერის მეხსიერებაში თითოეული რიცხვის წარმოდგენა შეზღუდულია გარკვეულინ ციფრების რაოდენობა, თითოეული ოპერაციის შესრულებისას ჩნდება შეცდომა დამ ამ შეცდომების მოსალოდნელი შედეგი დამოკიდებულია ფრჩხილების მოწყობაზე. დაე -მანქანა ნულოვანი . Ეს ნიშნავს, რომ. მაშინ სანამ.

მოდით აღვნიშნოთ ფრჩხილების მოწყობის შესაძლო გზების რაოდენობა. მერე

ოპერაციას პირობითად პროდუქტს ვუწოდებთ. თვითნებურად, ჩვენ ვყოფთ ფრჩხილების მოწყობის ყველა გზას კლასებად, მათ შორის - კლასში.მაგრამ ჭალა, პირველი და ბოლო ოპერანდების ნამრავლი გამოითვლება გარკვეული მანძილითმაგრამ ახალი ფრჩხილები და შემდეგ მათი პროდუქტი გამოითვლება:

(7)

სადაც.

განმარტებით, ფრჩხილების მოწყობის გზების რაოდენობა პირველი ოპერანდების გამოსათვლელად ტოლია, ბოლო - . პროდუქტის წესის მიხედვით, შეთანხმებების რაოდენობაშესახებ (4) გამოხატვის მხარე ტოლია. დამატების წესის მიხედვით

, (8)

Მაგალითად, .

1. ხაზოვანი განმეორებითი ურთიერთობები მუდმივი კოეფიციენტებით

(1) მიმართებაში ფუნქცია იყოს წრფენოე

, (9)

სად არის რამდენიმე ნომერი. ასეთ კოეფიციენტებს ე.წხაზოვანი თანაფარდობები რიგის ამონახსნები მუდმივი კოეფიციენტებით.

ჯერ დეტალურად განვიხილოთ მეორე რიგის ურთიერთობები და შემდეგ გადავიდეთ oბ მიმდინარე შემთხვევა. ზე, ფორმულიდან (9) ვიღებთ

, . (10)

ამ ურთიერთობების გადაწყვეტა ემყარება შემდეგ ადვილად დადასტურებულ განცხადებებსე ნიახ.

ლემა 1. მოდით იყოს (10) მიმართების ამონახსნი და იყოს ნებისმიერი რიცხვი. შემდეგ თანმიმდევრობაც იხსნებადა მიირთვით ეს თანაფარდობა.

ლემა 2. დაე და იყოს გადაწყვეტილებებიშესახებ გადაწყვეტილებები (10). შემდეგ თანმიმდევრობაც არისმე არის ამ ურთიერთობის გამოსავალი.

ეს ორი მარტივი ლემა მივყავართ შემდეგ მნიშვნელოვან დასკვნამდე. სკუპიპ ყველა შესაძლო მიმდევრობის არსებობა დასვენების ოპერაციებთანრ დინატური მიმატება და გამრავლება სკალარით ქმნის ვექტორულ სივრცეს. სკუპიპ მიმდევრობების რაოდენობა, რომლებიც არის მიმართების ამონახსნები (10) წარმოადგენსშესახებ ბრძოლა ამ სივრცის ქვესივრცეს. ყველა შესაძლო ჩამკეტი სივრცეშესახებ მიმდევრობები არის უსასრულო განზომილებიანი, მაგრამ ამონახსნების ქვესივრცე წრფივი განმეორებადით მიმართებას აქვს განტოლების რიგის ტოლი სასრული განზომილებაე ნია.

ლემა 3. განმეორებადი მიმართების ამოხსნის სივრცის განზომილება (10) უდრის ორს.

მე-3 ლემიდან გამომდინარეობს, რომ (12) განტოლების ყველა ამონახსნის დასადგენად საჭიროა ორი წრფივად დამოუკიდებელი ამონახსნის პოვნა. ნებისმიერი სხვა გამოსავალი იქნებაბ არის ამ ძირითადი გადაწყვეტილებების წრფივი კომბინაცია.

განვიხილოთ პირველი რიგის განმეორების მიმართება

, (11)

სადაც არის მუდმივი.

თუ, მაშინ (11)-დან გვაქვს

, (12)

ანუ პირველი რიგის რეკურსიული განტოლების ამონახსნი არის გეომეტრიული პროგრესია.

მეორე რიგის რეციდივის მიმართების ამოხსნას ვეძებთ ასევე ფორმაში (12). შემდეგ, (12) ჩანაცვლებით (9) ვიღებთ

. (13)

=0-სთვის გვაქვს ნულოვანი ამონახსნი, რომელიც არ არის საინტერესო. იმის გათვალისწინებით, ბოლო თანაფარდობას ვყოფთ:

(14)

ამრიგად, გეომეტრიული პროგრესია (12) არის გამოსავალი განმეორებითი მიმართების (10), თუ პროგრესიის მნიშვნელი არის კვადრატული განტოლების ფესვი.ე ნია (14). ეს განტოლება ე.წდამახასიათებელი განტოლებაგანმეორებითი კოოსთვის t ტარება (9).

ძირითადი ამონახსნების აგება დამოკიდებულია ფესვებზე და დამახასიათებელ განტოლებაზე (14).

1. (). ამ შემთხვევაში გვაქვს ორი გამოსავალი და რომელიც ლდა უცნობი სიმსი. ამის შესამოწმებლად, ჩვენ ვაჩვენებთ ამას ფორმულიდან

(15)

მუდმივთა შესაბამისი არჩევანით, (10) მიმართების ნებისმიერი ამონახსნის მიღება შეიძლება. განიხილეთ თვითნებური გადაწყვეტა. ჩვენ ვირჩევთ მუდმივებს და ასე რომ და:

(16)

ხაზოვანი სისტემის განმსაზღვრელი (16)

შესაბამისად, სისტემას აქვს უნიკალური გადაწყვეტა, რაც ნიშნავს, რომ ფორმულა (15) არის ზოგადი рე კავშირი (10).

1. . მრავალი ფესვის შემთხვევაში დამახასიათებელ განტოლებას (13) აქვს ფორმა ან. შემდეგ და მიმართებით (10) გვშესახებ ვიღებთ განტოლებას, რომელიც იძლევა ორ ძირითად ამონახს და. ზოგადი გამოსავალი წარმოდგენილია როგორც

. (17)

მე-2 რიგის მიმართების შემთხვევაში (9) ხდება მე-2 რიგის განტოლებისთვის განხილული დებულებების მსგავსი განცხადებები.

1. (9) განტოლების ყველა ამონახსნის სიმრავლე არის ქვესივრცე pr-შიშესახებ ყველა მიმდევრობის სივრცე.
2. ამ სივრცის განზომილება ტოლია, ანუ თითოეული გამოსავალი ცალსახად განისაზღვრება მისი პირველი მნიშვნელობებით.
3. გადაწყვეტილებების ქვესივრცის საფუძვლის დასადგენად, მახასიათებელი e განტოლება

. (18)

მრავალწევრი

(19)

დაურეკა დამახასიათებელი მრავალწევრირეკურსიული მიმართება (9).

1. თუ დამახასიათებელ განტოლებას განსხვავებული ფესვები აქვს, მაშინ განმეორებადი მიმართების (9) ზოგად ამოხსნას აქვს ფორმა

. (20)

ამოხსნის მოცემული საწყისი მნიშვნელობებისთვის, მუდმივები nმაგრამ სისტემიდან გასვლა

1. თუ არის დამახასიათებელი სიმრავლის განტოლების ფესვი, მაშინ მიმართებას (9) აქვს შემდეგი ამონახსნები

დაე, დამახასიათებელ განტოლებას (18) ჰქონდეს ფესვები: ,…, სიმრავლეებითშესახებ მეტიც, პასუხისმგებლობით... შემდეგ დამახასიათებელი ნაკრებიშესახებ (9) მიმართების ტერმინი და ზოგადი ამოხსნა წარმოდგენილია როგორც

მაგალითი 3. ბინეტის ფორმულა . დავსვათ h-სთვის ფორმულის გამოკვეთი სახით მიღების ამოცანადა იჯდა ფიბონაჩი. ამისათვის ჩვენ ვპოულობთ გამოსავალს რეციდივის მიმართებაში (4) იმ პირობით, რომ. ჩვენ ვადგენთ დამახასიათებელ განტოლებას, ვიპოვით მის ფესვებს და ვიღებთ ზოგად ამონახსანს. მუდმივები და განმარტებებიე ლიმი საწყისი პირობებიდან: . მერე ან

, (21)

სად არის ოქროს განყოფილება. ფორმულა (21) ე.წბინეტის ფორმულა . სადაც. ბინეტის ფორმულიდან გამომდინარეობს, რომ.

სხვა დაკავშირებული სამუშაოები, რომლებიც შეიძლება დაგაინტერესოთ.vshm>
3792.		კოეფიციენტების რაციონალურობა საწარმოს აქტივში	113.83 კბ
	ბალანსი ფინანსური ანგარიშგების ძირითადი ფორმაა. იგი ახასიათებს ორგანიზაციის ქონებრივ და ფინანსურ მდგომარეობას საანგარიშგებო თარიღისთვის. ბალანსი ასახავს ყველა სააღრიცხვო ანგარიშის ნაშთებს საანგარიშგებო თარიღისთვის. ეს მაჩვენებლები მოცემულია ბალანსში გარკვეულ ჯგუფში.
8407.		მუდმივი მეთოდი	17.82 კბ
	ობიექტის მეთოდს ეძახიან, რომ აქვს უცვლელობის (მუდმივობის) თვისება, თუ მისი შესრულების შემდეგ ობიექტის მდგომარეობა არ იცვლება. თუ თქვენ არ აკონტროლებთ უცვლელობის თვისებას, მაშინ მისი უზრუნველყოფა მთლიანად დამოკიდებული იქნება ოსტატობის უნარზე. პროგრამისტი. თუ უცვლელი მეთოდი წარმოქმნის ექსტრაორდინალურ ეფექტებს შესრულების დროს, მაშინ შედეგი შეიძლება იყოს ყველაზე მოულოდნელი და ძალიან რთულია ასეთი კოდის გამართვა და შენარჩუნება.
13457.		ფაზის სიბრტყის მეთოდი	892.42 კბ
	ფაზის სიბრტყის მეთოდი პირველად გამოიყენა ფრანგმა მეცნიერმა ანრი პუანკარემ არაწრფივი სისტემების შესასწავლად. ამ მეთოდის მთავარი უპირატესობაა არაწრფივი სისტემის მოძრაობების ანალიზის სიზუსტე და ხილვადობა. მეთოდი ხარისხობრივია
2243.		შესაძლო მიმართულებების მეთოდი	113.98 კბ
	შესაძლო MRI მიმართულებების მეთოდის იდეა არის ის, რომ ყოველი მომდევნო წერტილში არის დაშვების ისეთი მიმართულება, რომ ამ მიმართულებით წერტილის გადაადგილება გარკვეულ მანძილზე არ არღვევს პრობლემის შეზღუდვებს. ვექტორით განსაზღვრულ მიმართულებას ეწოდება შესაძლო მიმართულება იმ წერტილში, თუ მიმართულებიდან საკმარისად მცირე მოძრაობა არ აშორებს წერტილს m დასაშვები ფართობის გარეთ. ცხადია, თუ არის სიმრავლის შიდა წერტილი, მაშინ ამ მიმართულებით ნებისმიერი მიმართულება. წერტილი შესაძლებელია. შესაძლებელია...
12947.		ჰარმონიული LINEARIZATION მეთოდი	338.05 კბ
	უშუალოდ რომ მივმართოთ ჰარმონიული წრფივი მეთოდის განხილვას, ჩვენ ვივარაუდებთ, რომ შესასწავლი არაწრფივი სისტემა დაყვანილია იმ ფორმამდე, რომელიც ნაჩვენებია. არაწრფივ ელემენტს შეიძლება ჰქონდეს რაიმე მახასიათებელი, სანამ ის ინტეგრირებადია მეორე ტიპის წყვეტების გარეშე. ამ ცვლადის ტრანსფორმაცია, მაგალითად, არაწრფივი ელემენტით მკვდარი ზონით, ნაჩვენებია ნახ.
2248.		LLP-ის ამოხსნის გრაფიკული მეთოდი	219.13 კბ
	ამ ტერიტორიის შიგნით და საზღვარზე მდებარე პუნქტები მოქმედი თვითმფრინავია. კერძოდ, AB სეგმენტის ყველა წერტილი არის ამოცანის ოპტიმალური გეგმა, რომელზედაც მიიღწევა წრფივი ფორმის მაქსიმალური მნიშვნელობა. თანმიმდევრული გეგმის გაუმჯობესების მეთოდი მეთოდი ეფუძნება პრობლემური გეგმების სიმრავლის კუთხის წერტილების მოწესრიგებულ ჩამოთვლას წრფივი ფორმის გაზრდის ან შემცირების მიმართულებით და შეიცავს სამ არსებით წერტილს. პირველ რიგში, მითითებულია საბაზისო გამოთვლის მეთოდი.
7113.		ჰარმონიული ხაზინაარიზაციის მეთოდი	536.48 კბ
	ჰარმონიული წრფივობის მეთოდი ვინაიდან ეს მეთოდი მიახლოებითია, მიღებული შედეგები სიმართლესთან ახლოს იქნება მხოლოდ იმ შემთხვევაში, თუ დაკმაყოფილდება გარკვეული დაშვებები: არაწრფივი სისტემა უნდა შეიცავდეს მხოლოდ ერთ არაწრფივობას; სისტემის ხაზოვანი ნაწილი უნდა იყოს დაბალგამტარი ფილტრი, რომელიც აქვეითებს ზღვრულ ციკლში წარმოქმნილ მაღალ ჰარმონიებს; მეთოდი გამოიყენება მხოლოდ ავტონომიურ სისტემებზე. ჩვენ ვსწავლობთ სისტემის თავისუფალ მოძრაობას, ანუ მოძრაობას არანულოვანი საწყის პირობებში გარეგანი ზემოქმედების არარსებობის პირობებში....
10649.		ანალიზის ინდექსის მეთოდი	121.13 კბ
	ინდივიდუალური ინდექსები. ზოგადი აგრეგატული ინდექსები. საშუალო გადაყვანილი ინდექსები. სტრუქტურული ძვრების ცვლადი და მუდმივი შემადგენლობის ინდექსები.
12914.		მინიმალური კვადრატის მეთოდი	308.27 კბ
	მოდით, თეორიული მოსაზრებებიდან ვიცოდეთ ეს. აქედან გამომდინარე, შეგვიძლია ვთქვათ, რომ ჩვენი ამოცანაა სწორი ხაზის საუკეთესოდ დახაზვა. ჩვენ ვივარაუდებთ, რომ მთელი შეცდომა იმაში მდგომარეობს. ჩვენ გამოვარჩევთ სასურველ კოეფიციენტებს, რათა შემთხვევითი შეკრება იყოს ყველაზე პატარა.
9514.		აღრიცხვის მეთოდი	1002.23 კბ
	საბუღალტრო rahunki რომ їх pobudova. Vіn sladєtsya z რიგი elementіv golovnі z yakikh: დოკუმენტაცია; ინვენტარი; რაჰუნკი; ქვეჩანაწერი; შეფასება; გაანგარიშება; ბალანსი; სიმტკიცე. რაჰუნკის აღრიცხვა აღიარებულია აქტივებისა და ვალდებულებების არსებობის გამო. საბუღალტრო rahunki რომ їх pobudova.

განმეორებითი ურთიერთობები

განმეორებითი ურთიერთობები

(ლათ. recur-rens, genus case recurrentis - დაბრუნებული) - იგივე ტიპის f-ები, რომლებიც აკავშირებენ ერთმანეთის მიყოლებით გარკვეულ მიმდევრობას (ეს შეიძლება იყოს რიცხვების მიმდევრობა, f-tions და ა.შ.). რ-სთან დაკავშირებული ობიექტების ბუნებიდან გამომდინარე, ეს მიმართებები შეიძლება იყოს ალგებრული, ფუნქციური, დიფერენციალური, ინტეგრალური და სხვ.

ნაიბი. ცნობილი კლასის R. ს არის განმეორებადი ფუნქციები ამისთვის სპეციალური ფუნქციები.დიახ, ამისთვის ცილინდრული ფუნქციები Z m (x) პ. დან. გამოიყურება როგორც

ისინი ფუნქციით იძლევიან საშუალებას Z m0 (x) ფუნქციების პოვნა Z m (x)-ზე თ= თ 0 ბ 1, თ 0 ბ 2ან, მაგალითად, ფუნქციების მნიშვნელობების მიხედვით რაღაც მომენტში X 0 . 0 იპოვნეთ (ციფრულ გამოთვლებში) რომელიმე ფუნქციის მნიშვნელობა

ამავე დროს (აქ მ 0 - ნებისმიერი რეალური რიცხვი).

Dr. მნიშვნელოვანი კლასი რ ს. მიეცით თანმიმდევრული მიახლოების მრავალი მეთოდი (იხ. გამეორების მეთოდი);აქ არის მეთოდები თეორიის არეულობა.

კვანტურ მექანიკაში არსებობს R. s-ის სხვა ფორმა, რომელიც აკავშირებს ვექტორებს ჰილბერტის მდგომარეობებში. მაგალითად, სტაციონარული ჰარმონიები, ოსცილატორები პარამეტრიზებულია არაუარყოფითი მთელი რიცხვებით. შესაბამისი ვექტორები, რომლებიც აღინიშნება , სადაც ნ- მთლიანი, განსხვავებული ნერთმანეთისგან მიღება შესაძლებელია შექმნის ოპერატორების მოქმედებით a +და განადგურება მაგრამ:

ეს ურთიერთობები შეიძლება გადაწყდეს ნებისმიერი ვექტორის გამოხატვით (ყველაზე დაბალი ენერგეტიკული მდგომარეობა, თ = 0):

ამ კონსტრუქციის განზოგადება არის წარმოდგენა მეორე კვანტიზაციაკვანტურ სტატისტიკაში. მექანიკა და ველის კვანტური თეორია (იხ ფოკისივრცე).

ტიპიური მაგალითი რ. სტატისტიკაში მექანიკა - განტოლებები ნაწილობრივი განაწილების ფუნქციებისთვის, რომლებიც ქმნიან ბოგოლიუბოვის ჯაჭვს (იხ. ბოგოლიუბოვის განტოლებები);ასეთი f-ების ცოდნა საშუალებას გაძლევთ იპოვოთ ყველა თერმოდინამიკური. სისტემის მახასიათებლები.

ველის კვანტურ თეორიაში დინამიკა. შეიცავს, მაგალითად, გრინის ფუნქციები.მათი გაანგარიშებისთვის, სხვადასხვა მიახლოებები, ყველაზე ხშირად - პერტურბაციის თეორიის გამოთვლები. ალტერნატიული მიდგომა ეფუძნება ინტეგრო-დიფერენციალურს დაისონის განტოლებები,რომლებიც არის R. s.: ორპუნქტიანი გრინის ფუნქციის განტოლება შეიცავს ოთხპუნქტიან ერთს და ა.შ. ბოგოლიუბოვის განტოლების მსგავსად, ამ სისტემის ამოხსნა შესაძლებელია მხოლოდ ჯაჭვის "გაწყვეტით" ("შესვენების ადგილი" ჩვეულებრივ არჩეულია ფიზიკური მოსაზრებებიდან და განსაზღვრავს შედეგს).

სხვა ტიპის რ. ველის კვანტურ თეორიაში - იდენტობათა ურდოთეორიებში კალიბრაციის ველები.ეს იდენტობები ასევე წარმოადგენს ინტეგრო-დიფერენციალური მიმართებების ჯაჭვს, რომელიც აკავშირებს გრინის ფუნქციებს დეკ. გარე ხაზების რაოდენობა, p არის თეორიის ლიანდაგის უცვლელობის შედეგი. ისინი გადამწყვეტ როლს ასრულებენ პროცედურის დროს კალიბრაციის სიმეტრიის შემოწმებაში რენორმალიზაცია.

დაბოლოს, თავად არის ასევე განმეორებადი პროცედურა: ყოველ საფეხურზე (ყოველ მომდევნო ციკლში) კონტრტერმინები,მიღებული სქემების გაანგარიშებით ნაკლები მარყუჟებით (დაწვრილებით იხ R ოპერაცია).A. M. მალოკოსტოვი.

ფიზიკური ენციკლოპედია. 5 ტომად. - მ.: საბჭოთა ენციკლოპედია. მთავარი რედაქტორი A.M. პროხოროვი. 1988 .

ნახეთ, რა არის "რეკურენტული ურთიერთობები" სხვა ლექსიკონებში:

განმეორებადი ურთიერთობები- - [ლ.გ. სუმენკო. საინფორმაციო ტექნოლოგიების ინგლისური რუსული ლექსიკონი. M .: GP TsNIIS, 2003.] თემები საინფორმაციო ტექნოლოგიები ზოგადად EN განმეორებითი ურთიერთობები ... ტექნიკური მთარგმნელის სახელმძღვანელო

- (ვებერის ფუნქციები) ზოგადი სახელწოდება სპეციალური ფუნქციებისთვის, რომლებიც არის დიფერენციალური განტოლებების ამონახსნები, რომლებიც მიღებულია მათემატიკური ფიზიკის განტოლებისთვის ცვლადების გამოყოფის მეთოდის გამოყენებით, როგორიცაა ლაპლასის განტოლება, განტოლება ... ... ვიკიპედია.

ან ჯოზეფუსის რითმა არის ცნობილი მათემატიკური პრობლემა ისტორიული ელფერებით. დავალება ეფუძნება ლეგენდას, რომ იოსებ ფლავიუსის რაზმს, რომელიც იცავდა ქალაქ იოდფატს, არ სურდა დანებება რომაელთა ზემდგომ ძალებს, რომლებმაც გადაკეტეს გამოქვაბული. ... ... ვიკიპედია.

პაფნუტი ლვოვიჩ ჩებიშევი მათემატიკაში ნამდვილ მრავალწევრთა უსასრულო მიმდევრობას ორთოგონალური მრავალწევრების მიმდევრობა ეწოდება... ვიკიპედია

ეს სტატია შემოთავაზებულია წასაშლელად. მიზეზების ახსნა და შესაბამისი დისკუსია შეგიძლიათ იხილოთ ვიკიპედიის გვერდზე: წაიშლება / 22 ნოემბერი, 2012. სანამ განხილვის პროცესი ... ვიკიპედია

პადოვანის თანმიმდევრობა არის მთელი რიგი P(n) საწყისი მნიშვნელობებით და წრფივი რეციდივის მიმართებით. P(n)-ის პირველი მნიშვნელობებია 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265 ... ვიკიპედია

გარკვეული ფორმის ჰერმიტული პოლინომები არის მრავალწევრების თანმიმდევრობა ერთ რეალურ ცვლადში. ჰერმიტის პოლინომები წარმოიქმნება ალბათობის თეორიაში, კომბინატორიკასა და ფიზიკაში. ამ მრავალწევრებს ჩარლზ ჰერმიტის სახელი ჰქვია. სარჩევი 1 ... ... ვიკიპედია

- (ბესელის ფუნქციები) ბესელის განტოლების Zv(z) ამონახსნები, სადაც პარამეტრი (ინდექსი) v არის თვითნებური რეალური ან რთული რიცხვი. აპლიკაციებში ხშირად ხვდება განტოლება, რომელიც დამოკიდებულია ოთხ პარამეტრზე: ამონახსნები გამოიხატება C... ფიზიკური ენციკლოპედია

წრფივი ალგებრული სისტემის ამოხსნის მეთოდი. განტოლებები A x= b ჰერმიციული არასიგნორული მატრიცით A. პირდაპირ მეთოდებს შორის ის ყველაზე ეფექტურია კომპიუტერზე განხორციელებისას. მეთოდის გამოთვლითი სქემა ზოგადად ეფუძნება ჰერმიტის ფაქტორიზაციას ... ... მათემატიკური ენციკლოპედია

შეცვლილი ბესელის ფუნქციები არის წმინდა წარმოსახვითი არგუმენტის ბესელის ფუნქციები. თუ ბესელის დიფერენციალურ განტოლებაში ჩავანაცვლებთ, ის მიიღებს ფორმას ამ განტოლებას ეწოდება შეცვლილი ბესელის განტოლება... ვიკიპედია

რეციდივის მიმართება აქვს შეკვეთა კ , თუ ის იძლევა f(n+k) გამოხატვის საშუალებას f(n), f(n+1), …, f(n+k-1).

მაგალითი.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 არის მეორე რიგის განმეორებითი მიმართება.

f(n+3)=6f(n)f(n+2)+f(n+1) არის მესამე რიგის განმეორებადი მიმართება.

თუ kth რიგის განმეორებითი მიმართებაა მოცემული, მაშინ უსასრულოდ ბევრი თანმიმდევრობა შეიძლება დააკმაყოფილოს მას, ვინაიდან მიმდევრობის პირველი k ელემენტები შეიძლება თვითნებურად დაყენდეს - მათ შორის არ არის მიმართება. მაგრამ თუ პირველი k ტერმინები მოცემულია, მაშინ ყველა სხვა ელემენტი ცალსახად არის განსაზღვრული.

რეციდივის მიმართებისა და საწყისი ტერმინების გამოყენებით, შეიძლება სათითაოდ ამოვიწეროთ მიმდევრობის ტერმინები და ადრე თუ გვიან მივიღებთ მის რომელიმე წევრს. თუმცა, თუ თქვენ უნდა იცოდეთ თანმიმდევრობის მხოლოდ ერთი კონკრეტული წევრი, მაშინ არ არის რაციონალური გამოთვალოთ ყველა წინა. ამ შემთხვევაში უფრო მოსახერხებელია n-ე წევრის გამოთვლის ფორმულა.

რეციდივის მიმართების ამოხსნანებისმიერი მიმდევრობა, რომლისთვისაც მოცემული მიმართება იდენტურია, ეწოდება.

მაგალითი. მიმდევრობა 2, 4, 8, …, 2 n არის გამოსავალი f(n+2)=3∙f(n+1) – 2∙f(n).

მტკიცებულება. მიმდევრობის საერთო ტერმინია f(n)=2 n . ასე რომ, f(n+2)= 2 n+2, f(n+1)= 2n+1. ნებისმიერი n-ისთვის მოქმედებს იდენტურობა 2 n+2 =3∙2 n+1 – 2∙2 n. მაშასადამე, 2 n მიმდევრობის f(n+2)=3f(n+1) – 2f(n) ფორმულაში ჩანაცვლებისას, მიმართება სრულდება იდენტურად. მაშასადამე, 2 n არის მითითებული მიმართების ამოხსნა.

რეციდივის მიმართების ამოხსნა kth ბრძანება ეწოდება გენერალი, თუ ეს დამოკიდებულია k თვითნებურ მუდმივებზე α 1 , α 2 , … α k და ამ მუდმივების არჩევით, ამ მიმართების ნებისმიერი ამონახსნის მიღება შეიძლება.

მაგალითი. რეციდივის მიმართება მოცემულია: f(n+2)=5f(n+1)-6f(n). დავამტკიცოთ, რომ მის ზოგად ამოხსნას აქვს ფორმა: f(n)= α 2 n + β3 n .

1. ჯერ ვამტკიცებთ, რომ f(n)=α 2 n + β3 n თანმიმდევრობა არის განმეორებითი მიმართების ამოხსნა. ჩაანაცვლეთ ეს თანმიმდევრობა რეციდივის მიმართებაში.

f(n)= α 2 n + β 3 n, ამიტომ f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2, მაშინ

5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f( n+2).

რეციდივის მიმართება მოქმედებს, მაშასადამე, α 2 n + β 3 n არის ამ განმეორებითი მიმართების ამოხსნა.

2. დავამტკიცოთ, რომ f(n+2)=5f(n+1)–6f(n) მიმართების ნებისმიერი ამონახსნი შეიძლება დაიწეროს f(n)= α 2 n + β 3 n . მაგრამ მეორე რიგის რეციდივის მიმართების ნებისმიერი ამოხსნა ცალსახად განისაზღვრება მიმდევრობის პირველი ორი წევრის მნიშვნელობებით. აქედან გამომდინარე, საკმარისია იმის ჩვენება, რომ ნებისმიერი a=f(1) და b=f(2) არის α და β ისეთი, რომ 2 α +3 β =a და 4 α +9 β =b. ადვილი მისახვედრია, რომ განტოლებათა სისტემას აქვს ამონახსნი a და b-ის ნებისმიერი მნიშვნელობისთვის.

ამრიგად, f(n)= α 2 n + β 3 n არის განმეორებადი მიმართების ზოგადი ამონახსნები f(n+2)=5f(n+1)–6f(n).

ხაზოვანი განმეორებითი ურთიერთობები მუდმივი კოეფიციენტებით

არ არსებობს განმეორებითი ურთიერთობების გადაჭრის ზოგადი წესები, მაგრამ არსებობს განმეორებითი ურთიერთობების კლასი, რომლისთვისაც ცნობილია მათი გადაჭრის ალგორითმი. ეს არის წრფივი განმეორებადი მიმართებები მუდმივი კოეფიციენტებით, ე.ი. ტიპის თანაფარდობა:

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

ვიპოვოთ ზოგადი წრფივი რეციდივის მიმართების ამოხსნა პირველი რიგის მუდმივი კოეფიციენტებით.

პირველი რიგის მუდმივი კოეფიციენტებით წრფივი რეციდივის მიმართებას აქვს ფორმა: f(n+1)=c f(n).

მოდით f(1)=a, შემდეგ f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, მსგავსი f(4)=c 3 ∙a და ასე შემდეგ, გაითვალისწინეთ, რომ f(n)=cn -1 ∙f(1).

დავამტკიცოთ, რომ c n -1 ∙f(1) თანმიმდევრობა არის პირველი რიგის განმეორებითი მიმართების ამოხსნა. f(n)=c n -1 ∙f(1), ამიტომ f(n+1)=c n f(1). ამ გამოთქმის მიმართებაში ჩანაცვლებით, მივიღებთ იდენტობას c n f(1)=с∙ c n -1 ∙f(1).

ახლა უფრო დეტალურად განვიხილოთ წრფივი რეციდივის მიმართებები მეორე რიგის მუდმივ კოეფიციენტებთან , ანუ ფორმის მიმართებები

f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).

გაითვალისწინეთ, რომ ყველა მოსაზრება მართებულია უმაღლესი დონის ურთიერთობებისთვისაც.

გადაწყვეტის თვისებები:

1) თუ x n თანმიმდევრობა არის ამონახსნი (*), მაშინ a∙x n ასევე ამონახსნებია.

მტკიცებულება.

x n არის გამოსავალი (*), აქედან გამომდინარე x n +2 =C 1 x n +1 +C 2 x n. ტოლობის ორივე მხარეს ვამრავლებთ a-ზე. ვიღებთ a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n. ეს ნიშნავს, რომ ax n არის ამონახსნი (*).

2) თუ x n და y n მიმდევრობები ამონახსნებია (*), მაშინ x n +y n თანმიმდევრობა ასევე ამონახსნებია.

მტკიცებულება.

x n და y n არის ამონახსნები, ამიტომ შემდეგი იდენტობები მოქმედებს:

x n +2 \u003d C 1 x n +1 + C 2 x n.

y n +2 =C 1 y n +1 +C 2 y n.

დავამატოთ ორი ტოლობა ტერმინით:

xn +2 +yn +2 =С 1 ∙xn +1 +С 2 ∙xn + С 1 ∙yn +1 +С 2 ∙yn = С 1 ∙(xn +1 + yn +1)+С 2 ∙(xn +yn). ეს ნიშნავს, რომ x n +y n არის გამოსავალი (*).

3) თუ r 1 არის კვადრატული განტოლების ამონახსნი r 2 =С 1 r+С 2, მაშინ მიმდევრობა (r 1) n არის გამოსავალი (*).

r 1 არის კვადრატული განტოლების ამონახსნი r 2 =C 1 r+C 2, ანუ (r 1) 2 =C 1 r 1 +C 2 . გავამრავლოთ ტოლობის ორივე მხარე (r 1) n-ზე. მიიღეთ

r 1 2 r 1 n \u003d (C 1 r 1 + C 2) r n.

r 1 n +2 \u003d C 1 r 1 n +1 + C 2 r 1 n.

ეს ნიშნავს, რომ თანმიმდევრობა (r 1) n არის გამოსავალი (*).

ამ თვისებებიდან გამომდინარეობს გადაწყვეტის გზაწრფივი რეციდივის მიმართებები მეორე რიგის მუდმივ კოეფიციენტებთან:

1. შეადგინეთ დამახასიათებელი (კვადრატული) განტოლება r 2 =C 1 r+C 2 . ვიპოვოთ მისი ფესვები r 1, r 2. თუ ფესვები განსხვავებულია, მაშინ ზოგადი ამონახსნი არის f(n)= ar 1 n +βr 2 n .

2. იპოვეთ a და β კოეფიციენტები. მოდით f(0)=a, f(1)=b. განტოლებათა სისტემა

აქვს გამოსავალი ნებისმიერი a და b. ეს გადაწყვეტილებები არის

Დავალება . მოდი ვიპოვოთ ფიბონაჩის მიმდევრობის საერთო ტერმინის ფორმულა.

გამოსავალი . დამახასიათებელ განტოლებას აქვს ფორმა x 2 \u003d x + 1 ან x 2 -x-1 \u003d 0, მისი ფესვები არის რიცხვები, რაც ნიშნავს, რომ ზოგად ამოხსნას აქვს ფორმა f (n) \u003d . როგორც ადვილი მისახვედრია, საწყისი პირობებიდან f(0)=0, f(1)=1 გამოდის, რომ a=-b=1/Ö5 და, შესაბამისად, ფიბონაჩის მიმდევრობის ზოგადი ამონახსნის ფორმა აქვს. :

.

გასაკვირია, რომ ეს გამოთქმა იღებს მთელ მნიშვნელობებს n-ის ყველა ბუნებრივი მნიშვნელობებისთვის.