ความสัมพันธ์ที่เกิดซ้ำและการนำไปใช้ ความสัมพันธ์ที่เกิดซ้ำ

คำอธิบายประกอบ: ตำแหน่งที่ไม่มีการทำซ้ำ การจัดเรียงใหม่ การรวมกัน ความสัมพันธ์ที่เกิดซ้ำ วิธีพิสูจน์อีกวิธีหนึ่ง กระบวนการแบ่งพาร์ติชั่นต่อเนื่อง ภารกิจ: "ความยากลำบากสำหรับเมเจอร์โดโม"

ตำแหน่งที่ไม่มีการทำซ้ำ

มีรายการต่างๆ สามารถจัดได้กี่ตัว? ในกรณีนี้ การจัดเตรียมสองแบบจะถือว่าแตกต่างกันหากต่างกันในองค์ประกอบอย่างน้อยหนึ่งองค์ประกอบ หรือประกอบด้วยองค์ประกอบเดียวกัน แต่จัดเรียงในลำดับที่แตกต่างกัน การจัดเตรียมดังกล่าวเรียกว่า ตำแหน่งที่ไม่มีการทำซ้ำและหมายเลขของพวกเขาแสดงด้วย เมื่อรวบรวมตำแหน่งโดยไม่ต้องทำซ้ำรายการ เราจำเป็นต้องตัดสินใจเลือก ในขั้นตอนแรก คุณสามารถเลือกรายการใดก็ได้ที่มีอยู่ หากเลือกตัวเลือกนี้แล้ว ในขั้นตอนที่สอง คุณจะต้องเลือกจากรายการที่เหลือ ในขั้นที่ - ของวัตถุ ดังนั้นตามกฎผลคูณ เราพบว่าจำนวน -ตำแหน่งที่ไม่มีการซ้ำของวัตถุแสดงได้ดังนี้:

การจัดเรียงใหม่

เมื่อรวบรวมการเรียบเรียงโดยไม่มีการซ้ำซ้อนจากองค์ประกอบ เราได้รับการจัดเรียงที่แตกต่างกันทั้งองค์ประกอบและลำดับขององค์ประกอบ แต่ถ้าเราจัดการที่มีองค์ประกอบทั้งหมด องค์ประกอบเหล่านั้นก็จะสามารถแตกต่างกันได้เฉพาะตามลำดับองค์ประกอบที่รวมอยู่ในองค์ประกอบเหล่านั้นเท่านั้น การจัดเตรียมดังกล่าวเรียกว่า การเรียงสับเปลี่ยนขององค์ประกอบ nหรือเรียกสั้น ๆ ว่าการเรียงสับเปลี่ยน

การรวมกัน

ในกรณีที่เราไม่สนใจลำดับขององค์ประกอบในชุดค่าผสม แต่สนใจเฉพาะองค์ประกอบเท่านั้น เราจะพูดถึงชุดค่าผสม ดังนั้น การรวมกันขององค์ประกอบคือการจัดเรียงทุกประเภทที่ประกอบด้วยองค์ประกอบเหล่านี้ และมีความแตกต่างกันในการจัดองค์ประกอบ แต่ไม่เรียงตามลำดับขององค์ประกอบ จำนวนชุดค่าผสมที่สามารถประกอบด้วยองค์ประกอบจะแสดงด้วย

สูตรสำหรับจำนวนชุดค่าผสมได้มาจากสูตรสำหรับจำนวนตำแหน่ง อันที่จริง ก่อนอื่นมาเขียนทุกอย่างกันก่อน - การรวมกันขององค์ประกอบ จากนั้นจัดเรียงองค์ประกอบที่รวมอยู่ในแต่ละชุดใหม่ด้วยวิธีที่เป็นไปได้ทั้งหมด ในกรณีนี้ ปรากฎว่าทั้งหมดเป็นตำแหน่งขององค์ประกอบ แต่ละรายการเพียงครั้งเดียวเท่านั้น แต่คุณสามารถสร้างการผสมผสานจากแต่ละอย่างได้! การเรียงสับเปลี่ยน และจำนวนของชุดค่าผสมเหล่านี้จะเท่ากับ ดังนั้นสูตรจึงถูกต้อง

จากสูตรนี้เราจะพบว่า

ความสัมพันธ์ที่เกิดซ้ำ

เมื่อแก้ไขปัญหาเชิงรวมหลายๆ ปัญหา พวกเขาใช้วิธีการลดปัญหาที่กำหนดให้เหลือปัญหาที่เกี่ยวข้องกับวัตถุจำนวนน้อยกว่า วิธีการลดปัญหาที่คล้ายกันสำหรับวัตถุจำนวนน้อยเรียกว่า วิธีความสัมพันธ์การเกิดซ้ำ(จากภาษาละติน "recurrere" - "to return")

เราแสดงให้เห็นแนวคิดของความสัมพันธ์ที่เกิดซ้ำกับปัญหาคลาสสิกที่เกิดขึ้นราวๆ ปี 1202 โดยเลโอนาร์โดแห่งปิซา หรือที่รู้จักในชื่อฟีโบนักชี ความสำคัญของตัวเลขฟีโบนัชชีในการวิเคราะห์อัลกอริธึมเชิงผสมทำให้ตัวอย่างนี้ค่อนข้างเหมาะสม

Fibonacci วางปัญหาในรูปแบบของเรื่องราวเกี่ยวกับอัตราการเติบโตของประชากรกระต่ายภายใต้สมมติฐานดังต่อไปนี้ ทุกอย่างเริ่มต้นด้วยกระต่ายคู่หนึ่ง แต่ละคู่จะผสมพันธุ์หลังจากผ่านไปหนึ่งเดือน หลังจากนั้นแต่ละคู่จะออกลูกกระต่ายคู่ใหม่ทุกเดือน กระต่ายไม่เคยตายและการสืบพันธุ์ของพวกมันไม่เคยหยุดนิ่ง

กำหนดให้เป็นจำนวนคู่ของกระต่ายในประชากรหลังจากผ่านไปหลายเดือน และให้ประชากรนี้ประกอบด้วยคู่ลูกและคู่ "เก่า" นั่นก็คือ ดังนั้นในเดือนหน้าจะมีเหตุการณ์ดังต่อไปนี้เกิดขึ้น: . จำนวนประชากรสูงอายุในขณะนั้นจะเพิ่มขึ้นตามจำนวนการเกิดในขณะนั้น - คู่สามีภรรยาสูงอายุแต่ละคู่ในเวลาใดเวลาหนึ่งจะให้กำเนิดลูกหลาน ณ เวลาใดเวลาหนึ่ง รูปแบบนี้จะเกิดขึ้นซ้ำในเดือนหน้า:

เมื่อรวมความเท่าเทียมกันเหล่านี้เข้าด้วยกัน เราจะได้ความสัมพันธ์การเกิดซ้ำดังต่อไปนี้:

(7.1)

การเลือกเงื่อนไขเริ่มต้นสำหรับลำดับหมายเลขฟีโบนักชีนั้นไม่สำคัญ คุณสมบัติที่สำคัญของลำดับนี้ถูกกำหนดโดยความสัมพันธ์ที่เกิดซ้ำ เราจะถือว่า (บางครั้ง ).

ลองดูปัญหานี้แตกต่างออกไปเล็กน้อย.

กระต่ายคู่หนึ่งให้กำเนิดลูกกระต่ายสองตัว (ตัวเมียและตัวผู้) เดือนละครั้ง และกระต่ายแรกเกิดจะออกลูกเมื่อสองเดือนหลังคลอด ในหนึ่งปีจะมีกระต่ายกี่ตัวถ้ามีกระต่ายหนึ่งคู่เมื่อต้นปี?

จากเงื่อนไขของปัญหาตามมาว่าในหนึ่งเดือนจะมีกระต่ายสองคู่ หลังจากผ่านไปสองเดือน กระต่ายคู่แรกเท่านั้นที่จะออกลูก และจะมี 3 คู่ และอีกเดือนหนึ่งทั้งกระต่ายคู่ดั้งเดิมและกระต่ายคู่ที่ปรากฏตัวเมื่อสองเดือนก่อนจะออกลูก ดังนั้นจะมีกระต่ายทั้งหมด 5 คู่ ให้เราแสดงด้วยจำนวนกระต่ายคู่หลังจากเดือนนับจากต้นปี เห็นได้ชัดว่าในอีกไม่กี่เดือนจะมีคู่เหล่านี้และกระต่ายคู่แรกเกิดเพิ่มมากขึ้นเหมือนเมื่อสิ้นเดือนนั่นคือกระต่ายคู่มากขึ้น กล่าวอีกนัยหนึ่ง มีความสัมพันธ์การเกิดซ้ำ

(7.2)

เนื่องจาก ตามเงื่อนไข และ เราพบอย่างต่อเนื่อง

โดยเฉพาะอย่างยิ่ง, .

ตัวเลขที่ถูกเรียกว่า ตัวเลขฟีโบนัชชี- พวกเขามีคุณสมบัติที่ยอดเยี่ยมมากมาย ทีนี้ลองหานิพจน์สำหรับตัวเลขเหล่านี้ผ่าน ในการทำเช่นนี้ เราจะสร้างการเชื่อมโยงระหว่างตัวเลขฟีโบนัชชีกับปัญหาเชิงรวมกันต่อไปนี้

ค้นหาจำนวนลำดับที่ประกอบด้วยศูนย์และลำดับที่ไม่มีลำดับที่สองติดต่อกัน.

เพื่อสร้างการเชื่อมต่อนี้ลองใช้ลำดับดังกล่าวและเปรียบเทียบกระต่ายคู่หนึ่งตามกฎต่อไปนี้: อันที่สอดคล้องกับเดือนเกิดของหนึ่งในคู่ของ "บรรพบุรุษ" ของคู่นี้ (รวมถึงกระต่ายดั้งเดิมด้วย) และ ศูนย์จะสอดคล้องกับเดือนอื่นๆ ทั้งหมด ตัวอย่างเช่น ลำดับ 010010100010 กำหนด "ลำดับวงศ์ตระกูล" ต่อไปนี้: ทั้งคู่ปรากฏตัวเมื่อสิ้นเดือนที่ 11 พ่อแม่ของพวกเขาเมื่อสิ้นเดือนที่ 7 "ปู่" เมื่อสิ้นเดือนที่ 5 และ "ผู้ยิ่งใหญ่" -ปู่” เมื่อปลายเดือนที่สอง จากนั้นกระต่ายคู่ดั้งเดิมจะถูกเข้ารหัสด้วยลำดับ 000000000000

เป็นที่ชัดเจนว่าในกรณีนี้ สองหน่วยในแถวไม่สามารถปรากฏในลำดับใดๆ ได้ - คู่ที่เพิ่งปรากฏขึ้นไม่สามารถให้กำเนิดลูกหลานได้ในหนึ่งเดือนตามเงื่อนไข นอกจากนี้ ตามกฎที่กำหนด กระต่ายคู่ที่ต่างกันจะเรียงลำดับกันตามลำดับ และในทางกลับกัน กระต่ายสองคู่ที่ต่างกันมักจะมี "ลำดับวงศ์ตระกูล" ที่แตกต่างกันเสมอ เนื่องจากตามเงื่อนไข กระต่ายตัวเมียจะให้กำเนิดลูกหลานซึ่งประกอบด้วยเพียง กระต่ายคู่หนึ่ง

การเชื่อมต่อที่สร้างขึ้นแสดงให้เห็นว่าจำนวน -sequences ที่มีคุณสมบัติที่ระบุเท่ากับ

ตอนนี้ให้เราพิสูจน์ว่า

(7.3)

โดยที่ ถ้าเป็นคี่ และ ถ้าเป็นคู่ กล่าวอีกนัยหนึ่ง - ส่วนจำนวนเต็มของตัวเลข (ในอนาคตเราจะแสดงส่วนจำนวนเต็มของตัวเลขด้วย ; ดังนั้น ).

แท้จริงแล้ว มันคือจำนวนลำดับทั้งหมดของ 0 และ 1 โดยที่ไม่มี 1 สองอันอยู่ติดกัน จำนวนลำดับดังกล่าวซึ่งมีทั้งลำดับและศูนย์จะเท่ากับ เนื่องจากสิ่งนี้จะต้องทำ

ตัวเลขฟีโบนัชชี.

เมื่อแก้ไขปัญหาเชิงรวมหลายๆ ปัญหา พวกเขาใช้วิธีการลดปัญหาที่กำหนดให้เหลือเพียงปัญหาที่เกี่ยวข้องกับองค์ประกอบจำนวนน้อยกว่า ตัวอย่างเช่น คุณสามารถหาสูตรสำหรับจำนวนการเรียงสับเปลี่ยนได้:

นี่แสดงว่าสามารถลดให้เหลือแฟกทอเรียลของจำนวนที่น้อยกว่าได้เสมอ

ตัวอย่างที่ดีของการสร้างความสัมพันธ์ที่เกิดซ้ำคือปัญหาฟีโบนักชี ในหนังสือของเขาเมื่อปี 1202 นักคณิตศาสตร์ชาวอิตาลี ฟีโบนัชชี ได้นำเสนอปัญหาต่อไปนี้ กระต่ายคู่หนึ่งให้กำเนิดลูกกระต่ายสองตัว (ตัวเมียและตัวผู้) เดือนละครั้ง และกระต่ายแรกเกิดเองก็ให้กำเนิดลูกสองเดือนหลังคลอด ในหนึ่งปีจะมีกระต่ายกี่ตัวหากในตอนแรกมีกระต่ายหนึ่งคู่

จากเงื่อนไขของปัญหาพบว่าในหนึ่งเดือนจะมีกระต่าย 2 คู่ ในอีก 2 เดือนกระต่ายคู่แรกที่ปรากฏตัวเมื่อ 2 เดือนที่แล้วเท่านั้นที่จะออกลูก ดังนั้นจะมีกระต่ายทั้งหมด 3 คู่ อีกเดือนก็จะ 5 คู่แล้ว และอื่นๆ

ให้เราแสดงด้วยจำนวนกระต่ายคู่หลังจากเดือนนับจากต้นปี หลังจากนั้นหนึ่งเดือนคุณจะพบจำนวนกระต่ายคู่ได้โดยใช้สูตร:

การพึ่งพานี้เรียกว่า ความสัมพันธ์ที่เกิดซ้ำ - คำว่า "การเรียกซ้ำ" หมายถึงการย้อนกลับ (ในกรณีของเรา การย้อนกลับไปยังผลลัพธ์ก่อนหน้า)

ตามเงื่อนไข และ จากนั้นโดยความสัมพันธ์เรามี: , , ฯลฯ., .

คำจำกัดความ 1:ตัวเลขที่ถูกเรียกว่า ตัวเลขฟีโบนัชชี - นี่คือลำดับตัวเลขที่รู้จักกันดีในวิชาคณิตศาสตร์:

1, 1, 2, 3, 5, 8, 13, 21, ...

ในลำดับนี้ แต่ละตัวเลขที่ตามมาคือผลรวมของตัวเลขสองตัวก่อนหน้า และในความสัมพันธ์การเกิดซ้ำ เทอมที่ตามมาจะพบว่าเป็นผลรวมของสองเทอมก่อนหน้าด้วย

ให้เราสร้างการเชื่อมโยงระหว่างหมายเลขฟีโบนัชชีกับปัญหาเชิงรวมกัน สมมติว่าเราจำเป็นต้องค้นหาลำดับจำนวนหนึ่งที่ประกอบด้วยศูนย์และลำดับที่ไม่มีลำดับใดอยู่ติดกัน

ลองใช้ลำดับดังกล่าวและจับคู่กระต่ายคู่หนึ่งตามกฎต่อไปนี้: อันที่สอดคล้องกับเดือนเกิดของหนึ่งในคู่ของ "บรรพบุรุษ" ของคู่นี้ (รวมถึงอันดั้งเดิมด้วย) และศูนย์จะสอดคล้องกับเดือนอื่น ๆ ทั้งหมด เดือน ตัวอย่างเช่นลำดับดังกล่าวสร้าง "ลำดับวงศ์ตระกูล" - ทั้งคู่ปรากฏตัวเมื่อสิ้นเดือนที่ 11 พ่อแม่ของมันเมื่อสิ้นเดือนที่ 7 "ปู่" เมื่อสิ้นเดือนที่ 5 และ "ผู้ยิ่งใหญ่" -ปู่” ปลายเดือนที่ 2 คู่เริ่มต้นจะถูกเข้ารหัสด้วยลำดับ ทั้งสองหน่วยไม่สามารถยืนเรียงกันเป็นลำดับได้ - คู่ที่เพิ่งปรากฏตัวไม่สามารถให้กำเนิดบุตรได้ภายในหนึ่งเดือน แน่นอนว่าลำดับที่ต่างกันจะสอดคล้องกับคู่ที่ต่างกันและในทางกลับกัน

ดังนั้น จำนวนลำดับที่มีคุณสมบัติที่ระบุจึงเท่ากับ

ทฤษฎีบท 1:พบตัวเลขเป็นผลรวมของสัมประสิทธิ์ทวินาม: ถ้า – แปลกแล้ว ถ้า - เท่ากันแล้ว มิฉะนั้น: – ส่วนจำนวนเต็มของตัวเลข

การพิสูจน์:แท้จริงแล้ว คือจำนวนลำดับทั้งหมดของ 0 และ 1 ที่ไม่มี 1 สองอันอยู่ติดกัน จำนวนของลำดับดังกล่าวที่มีทั้งเลขและศูนย์จะเท่ากับ จากนั้นจะแปรผันตั้งแต่ 0 ถึง เมื่อใช้กฎผลรวม เราจะได้ผลรวมนี้

ความเท่าเทียมกันนี้สามารถพิสูจน์ได้แตกต่างออกไป เรามาแสดงว่า:

จากความเท่าเทียมกันจึงเป็นไปตามนั้น อีกทั้งเป็นที่ชัดเจนว่า เนื่องจากทั้งสองลำดับและตอบสนองความสัมพันธ์ที่เกิดซ้ำแล้ว และ

คำจำกัดความ 2:ความสัมพันธ์ที่เกิดซ้ำมี คำสั่ง หากอนุญาตให้คำนวณผ่านสมาชิกก่อนหน้าของลำดับ:

ตัวอย่างเช่น เป็นความสัมพันธ์ที่เกิดซ้ำของลำดับที่ 2 และความสัมพันธ์ที่เกิดซ้ำของลำดับที่ 3 อัตราส่วนฟีโบนัชชีเป็นความสัมพันธ์ลำดับที่สอง

คำจำกัดความ 3: โดยวิธีแก้ปัญหาความสัมพันธ์ที่เกิดซ้ำเป็นลำดับที่เป็นไปตามความสัมพันธ์นี้

ถ้าให้ความสัมพันธ์การเกิดซ้ำของลำดับ ก็จะเป็นไปตามลำดับต่างๆ มากมายนับไม่ถ้วน เพราะ องค์ประกอบแรกสามารถตั้งค่าได้ตามอำเภอใจ แต่ถ้าให้องค์ประกอบแรก เงื่อนไขที่เหลือจะถูกกำหนดโดยไม่ซ้ำกัน

ตัวอย่างเช่น นอกเหนือจากลำดับ 1, 1, 2, 3, 5, 8, 13, 21, ... ที่กล่าวถึงข้างต้นแล้ว อัตราส่วนฟีโบนัชชียังสามารถตอบสนองด้วยลำดับอื่นๆ ได้อีกด้วย ตัวอย่างเช่น ลำดับที่ 2, 2, 4, 8, 12,... ถูกสร้างขึ้นตามหลักการเดียวกัน แต่ถ้าคุณระบุเงื่อนไขเริ่มต้น (มี 2 คำในลำดับฟีโบนัชชี) คำตอบก็จะถูกกำหนดโดยไม่ซ้ำกัน เงื่อนไขเริ่มต้นจำนวนมากถือเป็นลำดับของความสัมพันธ์

การใช้ความสัมพันธ์การเกิดซ้ำที่ทราบและเงื่อนไขเริ่มต้น เราสามารถเขียนเงื่อนไขของลำดับทีละรายการได้ และด้วยวิธีนี้เราจะได้เงื่อนไขใดๆ ก็ตาม แต่ในหลายกรณี เราไม่ต้องการสมาชิกก่อนหน้านี้ทั้งหมด แต่ต้องการสมาชิกเฉพาะเพียงคนเดียว ในกรณีนี้ จะสะดวกกว่าที่จะมีสูตรสำหรับเทอมที่ 3 ของลำดับ

เราจะบอกว่าลำดับใดลำดับหนึ่งเป็นคำตอบของความสัมพันธ์การเกิดซ้ำที่กำหนด หากเมื่อแทนที่ลำดับนี้แล้ว ความสัมพันธ์ก็จะเป็นไปตามที่พอใจเหมือนกัน

ตัวอย่างเช่น ลำดับเป็นหนึ่งในคำตอบของความสัมพันธ์: นี่เป็นเรื่องง่ายที่จะตรวจสอบด้วยการทดแทนแบบง่ายๆ

คำจำกัดความ 4:วิธีแก้ไขความสัมพันธ์การเกิดซ้ำของลำดับที่ th เรียกว่า ทั่วไป ถ้ามันขึ้นอยู่กับค่าคงตัวใดๆ ที่เปลี่ยนแปลง เราสามารถหาคำตอบใดๆ ของความสัมพันธ์นี้ได้

ตัวอย่างเช่น สำหรับความสัมพันธ์นั้น คำตอบทั่วไปจะเป็น

ในความเป็นจริง มันง่ายที่จะตรวจสอบว่ามันจะเป็นวิธีแก้ปัญหาความสัมพันธ์ของเรา ให้เราแสดงให้เห็นว่าสามารถรับวิธีแก้ปัญหาใด ๆ ได้ในแบบฟอร์มนี้ ปล่อยให้พวกเขาเป็นไปตามอำเภอใจ

แล้วจะมีผู้ที่

แน่นอนว่า สำหรับระบบสมการใดๆ ระบบสมการจะมีคำตอบเฉพาะตัว

คำจำกัดความ 5:เรียกว่าความสัมพันธ์การเกิดซ้ำ เชิงเส้น หากเขียนอยู่ในรูป:

ค่าสัมประสิทธิ์ตัวเลขอยู่ที่ไหน

โดยทั่วไปแล้ว ไม่มีกฎทั่วไปในการแก้ไขความสัมพันธ์ที่เกิดซ้ำตามอำเภอใจ อย่างไรก็ตาม มีกฎการแก้ปัญหาทั่วไปสำหรับการแก้ไขความสัมพันธ์การเกิดซ้ำเชิงเส้น

ให้เราพิจารณาความสัมพันธ์ลำดับที่ 2 ก่อน

วิธีแก้ไขความสัมพันธ์นี้ขึ้นอยู่กับข้อความต่อไปนี้

ทฤษฎีบท 2:ถ้า และ - เป็นคำตอบของความสัมพันธ์ที่เกิดซ้ำของลำดับที่ 2 ดังนั้นสำหรับตัวเลขใดๆ และลำดับก็ถือเป็นคำตอบของความสัมพันธ์นี้เช่นกัน

ทฤษฎีบท 3:ถ้าตัวเลขเป็นรากของสมการกำลังสอง ลำดับนั้นจะเป็นคำตอบของความสัมพันธ์การเกิดซ้ำ

จากทฤษฎีบท 2, 3 กฎต่อไปนี้สำหรับการแก้ไขความสัมพันธ์การเกิดซ้ำเชิงเส้นของลำดับที่ 2 มีดังนี้

ให้ความสัมพันธ์เกิดซ้ำได้รับ

1) มาสร้างสมการกำลังสองกันดีกว่า ซึ่งเรียกว่า ลักษณะเฉพาะ สำหรับอัตราส่วนที่กำหนด มาหากัน. ทั้งหมดรากของสมการนี้ (แม้จะมีหลายรายการและซับซ้อนก็ตาม)

2) มาสร้างวิธีแก้ปัญหาทั่วไปสำหรับความสัมพันธ์การเกิดซ้ำกัน โครงสร้างของมันขึ้นอยู่กับประเภทของราก (เหมือนหรือต่างกัน)

ก) หากความสัมพันธ์นี้มีสอง รากต่างๆและคำตอบทั่วไปของความสัมพันธ์จะมีรูปแบบ

แน่นอนจากทฤษฎีบท 2, 3 ตามนั้น - คำตอบและระบบสมการ

มีทางแก้ทางเดียวเพราะว่า ระบุว่า

ตัวอย่างเช่น สำหรับตัวเลข Fibonacci เรามี สมการคุณลักษณะมีรูปแบบ: . การแก้สมการสุดท้ายเราได้ราก:, .

หากรากทั้งหมดของสมการคุณลักษณะต่างกัน คำตอบทั่วไปจะมีรูปแบบ:

ตัวอย่างเช่นหากรูทนี้สอดคล้องกับวิธีแก้ปัญหา:

ของความสัมพันธ์ที่เกิดซ้ำนี้ ในวิธีแก้ปัญหาทั่วไป รูตนี้สอดคล้องกับส่วน

ตัวอย่างเช่น, การแก้ความสัมพันธ์การเกิดซ้ำ:

เราเขียนสมการลักษณะเฉพาะของแบบฟอร์ม: .

รากของมันคือ... ดังนั้นจึงมีวิธีแก้ปัญหาทั่วไป

การคำนวณเชิงผสมบนเซตจำกัด

ความรู้เบื้องต้นเกี่ยวกับเชิงผสม

หัวข้อของทฤษฎีอัลกอริธึมเชิงผสมผสาน ซึ่งมักเรียกว่าการคำนวณแบบผสมผสาน คือการคำนวณบนโครงสร้างทางคณิตศาสตร์ที่ไม่ต่อเนื่อง ในทฤษฎีนี้ มีการให้ความสนใจเป็นอย่างมากกับแนวทางอัลกอริธึมในการแก้ปัญหาทางคณิตศาสตร์แบบแยกส่วน การเลือกตัวเลือกให้เหมาะสม และลดจำนวนวิธีแก้ปัญหาที่กำลังพิจารณา

สาขาอัลกอริธึมเชิงผสมผสานรวมถึงปัญหาที่ต้องนับ (ประมาณ) จำนวนองค์ประกอบในชุดจำกัดหรือแสดงรายการองค์ประกอบเหล่านี้ตามลำดับพิเศษ (ภาคผนวก B) ในกรณีนี้มีการใช้ขั้นตอนในการเลือกองค์ประกอบที่มีการส่งคืนและตัวแปรต่างๆ อย่างกว้างขวาง

ปัญหาการนับมีสองประเภท ในกรณีธรรมดา จะมีการระบุชุดเฉพาะและจำเป็นต้องมี กำหนดจำนวนองค์ประกอบให้แน่ชัดในตัวเขา. ในกรณีทั่วไป จะมีกลุ่มของชุดที่กำหนดโดยพารามิเตอร์บางตัว และจำนวนสมาชิกของชุดจะถูกกำหนดเป็นฟังก์ชันของพารามิเตอร์ ในขณะเดียวกันก็มักจะเกิดขึ้น การประมาณลำดับของฟังก์ชันอย่างเพียงพอและบางครั้งคุณก็แค่ต้องการเท่านั้น การประมาณอัตราการเติบโต- ตัวอย่างเช่น หากพลังของเซตที่จะพิจารณาเพิ่มขึ้นแบบทวีคูณตามพารามิเตอร์บางตัว ก็อาจเพียงพอที่จะละทิ้งแนวทางที่เสนอในการศึกษาปัญหาโดยไม่ต้องจัดการกับรายละเอียดต่างๆ ขั้นตอนของการขยายเส้นกำกับ ความสัมพันธ์การเกิดซ้ำ และฟังก์ชันการสร้างจะนำไปใช้กับปัญหาทั่วไปประเภทนี้

อะซิมโทติกส์

เส้นกำกับคือเส้นพิเศษ (ส่วนใหญ่มักเป็นเส้นตรง) ที่เป็นขีดจำกัดของเส้นโค้งที่กำลังพิจารณา

เส้นกำกับเป็นศิลปะของการประมาณและเปรียบเทียบอัตราการเติบโตของฟังก์ชัน พวกเขาบอกว่าเมื่อ เอ็กซ์ฟังก์ชัน ®¥ "มีลักษณะการทำงานเหมือน เอ็กซ์" หรือ "เพิ่มขึ้นในอัตราเดียวกับ เอ็กซ์", และเมื่อ เอ็กซ์®0 "มีพฤติกรรมเหมือน 1/ x" พวกเขาบอกว่า "ล็อก xที่ x®0 และ e>0 ใดๆ มีพฤติกรรมเช่นนี้ x e และอะไรใน n®¥เติบโตไม่เร็วไปกว่า nบันทึก n"ข้อความที่ไม่ชัดเจนแต่ใช้สัญชาตญาณดังกล่าวมีประโยชน์ในการเปรียบเทียบฟังก์ชันเช่นเดียวกับอัตราส่วน<, £ и = при сравнивании чисел.

ให้เรากำหนดความสัมพันธ์เชิงเส้นกำกับหลักสามประการ

คำจำกัดความ 1.การทำงาน ฉ(x) เทียบเท่ากัน ก(x) ที่ เอ็กซ์® x 0ถ้าหากว่า =1

ในกรณีนี้เรียกว่าฟังก์ชัน ฉ(x) เท่ากับฟังก์ชันเชิงซีมโทติคัล ก(x) หรืออะไร ฉ(x) เติบโตในอัตราเดียวกับ ก(x).

คำจำกัดความ 2. ฉ(x)=o( ก(x)) ที่ x® x 0ถ้าหากว่า =0

พวกเขาบอกว่าเมื่อ x® x 0 ฟ(x) เติบโตช้ากว่า ก(x), หรืออะไร ฉ(x) "มีน้อย" จาก ก(x).

คำจำกัดความ 3 . ฉ(x)=โอ( ก(x)) ที่ x® x 0ถ้าหากมีค่าคงที่ C ซึ่งจะทำให้ sup = C

ในกรณีนี้พวกเขาพูดอย่างนั้น ฉ(x) เติบโตไม่เร็วกว่า ก(x), หรืออะไร x® x 0 ฟ(x) "มีโอใหญ่" จาก ก(x).

อัตราส่วน ฉ(x)=ก(x)+โอ(ชม.(x)) ที่ x®¥ หมายความว่าอย่างนั้น ฉ(x)-ก(x)=o(ชม.(x)). เช่นเดียวกัน ฉ(x)=ก(x)+เกี่ยวกับ(ชม.(x)) หมายความว่า ฉ(x)-ก(x)=อ(ชม.(x)).

นิพจน์ O(·) และ o(·) สามารถใช้ในอสมการได้เช่นกัน ตัวอย่างเช่นความไม่เท่าเทียมกัน x+โอ(x)2 ปอนด์ xที่ x®0 หมายความว่าสำหรับฟังก์ชันใดๆ ฉ(x) ดังนั้น ฉ(x)=o(x), ที่ x®¥ ความสัมพันธ์ยังคงอยู่ x+ฉ(x)2 ปอนด์ xสำหรับค่าทั้งหมดที่มีขนาดใหญ่เพียงพอ เอ็กซ์.

ให้เรานำเสนอความเท่าเทียมกันเชิงซีมโทติคที่มีประโยชน์

พหุนามมีค่าเท่ากับพจน์นำหน้าเชิงเส้นกำกับ:

ที่ x; (4.1)

ที่ x; (4.2)

ที่ x®¥ และ เค#0. (4.3)

ผลรวมของกำลังของจำนวนเต็มเป็นไปตามความสัมพันธ์:

ที่ n. (4.4)

ดังนั้นเราจึงมีเพื่อ n®¥

ในกรณีทั่วไปมากขึ้น เมื่อ n®¥ และสำหรับจำนวนเต็มใดๆ เค³0

; (4.6)

. (4.7)

ความสัมพันธ์ที่เกิดซ้ำ

เราแสดงให้เห็นแนวคิดของความสัมพันธ์แบบเกิดซ้ำโดยใช้ปัญหาคลาสสิกที่ Fibonacci ตั้งขึ้นและศึกษาในช่วงประมาณปี 1200

Fibonacci วางปัญหาของเขาในรูปแบบของเรื่องราวเกี่ยวกับอัตราการเติบโตของประชากรกระต่ายภายใต้สมมติฐานดังต่อไปนี้ ทุกอย่างเริ่มต้นด้วยกระต่ายคู่หนึ่ง กระต่ายแต่ละคู่จะผสมพันธุ์หลังจากผ่านไปหนึ่งเดือน หลังจากนั้นแต่ละคู่จะออกลูกกระต่ายคู่ใหม่ทุกเดือน กระต่ายไม่เคยตายและการสืบพันธุ์ของพวกมันไม่เคยหยุดนิ่ง อนุญาต ฟน- จำนวนคู่กระต่ายในประชากรหลังจากนั้น nเดือน และให้ประชากรกลุ่มนี้ประกอบด้วย เลขที่คู่ลูกหลานและ บนคู่ "เก่า" เช่น ฟน = เลขที่ + บน- ดังนั้นในเดือนหน้าจะมีเหตุการณ์ดังต่อไปนี้:

ประชากรเก่าใน ( n+1)ช่วงเวลาที่จะเพิ่มขึ้นตามจำนวนการเกิดในขณะนั้น n, เช่น. โอ้+1 = บน + เลขที่= ฟน;

เก่าทุกอันในชั่วขณะหนึ่ง nทั้งคู่ผลิตในเวลา ( n+1) ลูกหลานคู่หนึ่งเช่น นะ+1= ซีเอ็น.

รูปแบบนี้จะเกิดขึ้นซ้ำในเดือนหน้า:

โอ้+2 = โอ้+1+ นะ+1= Fn+1,

NN+2=โอ้+1;

เมื่อรวมความเท่าเทียมกันเหล่านี้เข้าด้วยกัน เราจะได้ความสัมพันธ์การเกิดซ้ำของ Fibonacci:

โอ้+2 + NN+2=Fn+1 + โอ้+1,

Fn+2 = Fn+1 + ฟน. (4.8)

การเลือกเงื่อนไขเริ่มต้นสำหรับลำดับหมายเลขฟีโบนักชีนั้นไม่สำคัญ คุณสมบัติที่สำคัญของลำดับนี้ถูกกำหนดโดยความสัมพันธ์ที่เกิดซ้ำ (4.8) ก็มักจะเชื่อกันว่า เอฟ 0=0, ฉ 1=1 (บางครั้งก็ถือว่า เอฟ 0=ฉ 1=1).

ความสัมพันธ์การเกิดซ้ำ (4.8) เป็นกรณีพิเศษของความสัมพันธ์การเกิดซ้ำเชิงเส้นที่เป็นเนื้อเดียวกันโดยมีค่าสัมประสิทธิ์คงที่:

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

ค่าสัมประสิทธิ์อยู่ที่ไหน ฉันไม่ต้องพึ่ง nและ x1, x2, …, เอ็กซ์เคถือว่าได้รับ

มีวิธีแก้ไขทั่วไป (เช่น การหา เอ็กซ์เอ็นเป็นฟังก์ชัน n) ความสัมพันธ์การเกิดซ้ำเชิงเส้นกับค่าสัมประสิทธิ์คงที่ ลองพิจารณาวิธีนี้โดยใช้ความสัมพันธ์ (4.8) เป็นตัวอย่าง เรามาหาวิธีแก้ไขกันในรูปแบบ

ฟน=Cr (4.10)

มีค่าคงที่ กับและ ร- เมื่อแทนนิพจน์นี้เป็น (4.8) เราจะได้

cr n + 2 = ซีอาร์เอ็น+ 1 + Cr,

Cr(ร n -r-1)=0. (4.11)

มันหมายความว่าอย่างนั้น ฟน=Crเป็นวิธีแก้ปัญหาหากอย่างใดอย่างหนึ่ง กับ=0 หรือ ร= 0 (และด้วยเหตุนี้ F n =0 สำหรับทุกคน n) และด้วย (และนี่เป็นกรณีที่น่าสนใจกว่า) ถ้า ร 2 - r -1=0 และค่าคงที่ กับโดยพลการ จากนั้นจาก (4.11) จะเป็นดังนี้

ร= หรือ ร = . (4.12)

ตัวเลข “1.618” เรียกว่าอัตราส่วน “ทองคำ” เนื่องจากเชื่อกันมาตั้งแต่สมัยโบราณว่ารูปสามเหลี่ยม (สี่เหลี่ยม) ที่มีด้าน 1 มีสัดส่วนที่สบายตามากที่สุด

ผลรวมของคำตอบทั้งสองต่อความสัมพันธ์การเกิดซ้ำเชิงเส้นแบบเอกพันธ์เห็นได้ชัดว่าเป็นคำตอบเช่นกัน และอันที่จริงแล้วสามารถแสดงให้เห็นได้ว่าคำตอบทั่วไปของลำดับฟีโบนัชชีคือ

ฟน= , (4.13)

ค่าคงที่อยู่ที่ไหน กับและ กับ'ถูกกำหนดโดยเงื่อนไขเริ่มต้น เมื่อใส่ F 0 =0 และ F 1 =1 เราจะได้ระบบสมการเชิงเส้นต่อไปนี้:

, (4.14)

วิธีแก้ปัญหาที่ให้

ค = -ค" = . (4.15)

ความสัมพันธ์ที่เกิดซ้ำ

ความสัมพันธ์ที่เกิดซ้ำ

(จาก lat. recur-rens, gen. case recurrentis - returning) - f-lys ประเภทเดียวกันซึ่งเชื่อมต่อลำดับบางอย่างที่ตามมาซึ่งกันและกัน (ซึ่งอาจเป็นลำดับของตัวเลขฟังก์ชัน ฯลฯ ) ขึ้นอยู่กับลักษณะของวัตถุที่เกี่ยวข้องกับระบบ ความสัมพันธ์เหล่านี้อาจเป็นพีชคณิต ฟังก์ชัน อนุพันธ์ อินทิกรัล ฯลฯ

นาอิบ. คลาสที่รู้จักกันดีของ R.s. เป็นฟังก์ชันที่เกิดซ้ำสำหรับ ฟังก์ชั่นพิเศษใช่สำหรับ ฟังก์ชันทรงกระบอก Z m (x)ป. กับ. ดูเหมือน

อนุญาตตามหน้าที่ Z m0 (x) ค้นหาฟังก์ชัน Zm(x)ที่ ต= ต 0 ข 1, ต 0 ข 2ฯลฯ หรือตามค่าฟังก์ชัน ณ จุดหนึ่ง เอ็กซ์ 0 . 0 ค้นหา (ในการคำนวณเชิงตัวเลข) ค่าของฟังก์ชันใด ๆ

ณ จุดเดียวกัน (นี่. ม 0 - จำนวนจริงใดๆ)

ดร. คลาสสำคัญของร.ส. ให้วิธีการประมาณค่าต่อเนื่องกันหลายวิธี (ดู วิธีการวนซ้ำ);รวมวิธีการไว้ที่นี่ด้วย ทฤษฎีการก่อกวน

ในกลศาสตร์ควอนตัม มีระบบไดนามิกอีกประเภทหนึ่งที่เชื่อมโยงเวกเตอร์ในปริภูมิฮิลแบร์ตของรัฐ ตัวอย่างเช่น ออสซิลเลเตอร์ฮาร์โมนี่แบบคงที่จะถูกกำหนดพารามิเตอร์ด้วยจำนวนเต็มที่ไม่เป็นลบ เวกเตอร์ที่สอดคล้องกันแสดงโดย , โดยที่ n- ทั้งหมดด้วยความแตกต่าง nจะได้รับจากกันโดยการกระทำของผู้ให้กำเนิด +และการทำลายล้าง ก:

ความสัมพันธ์เหล่านี้สามารถแก้ไขได้โดยการแสดงเวกเตอร์ใดๆ ในรูปของ (สถานะพลังงานต่ำสุด ชั่วโมง = 0):

ลักษณะทั่วไปของการก่อสร้างนี้คือการเป็นตัวแทน การหาปริมาณรองในสถิติควอนตัม กลศาสตร์และทฤษฎีสนามควอนตัม (ดู โฟก้าช่องว่าง).

ตัวอย่างทั่วไปของ R. s. ในทางสถิติ กลศาสตร์ - สมการสำหรับฟังก์ชันการกระจายบางส่วนที่ก่อตัวเป็นโซ่ Bogolyubov (ดู สมการโบโกลิโบฟ);ความรู้เกี่ยวกับฟังก์ชันดังกล่าวช่วยให้คุณค้นหาอุณหพลศาสตร์ทั้งหมดได้ ลักษณะระบบ

ในทฤษฎีสนามควอนตัม ไดนามิก มีอยู่เช่นใน หน้าที่ของกรีนในการคำนวณให้ใช้ต่างๆ การประมาณค่าบ่อยที่สุด - การคำนวณโดยใช้ทฤษฎีการก่อกวน อีกแนวทางหนึ่งจะขึ้นอยู่กับผลต่างปริพันธ์ สมการไดสันซึ่งเป็นระบบ R. สมการของฟังก์ชันสองจุดของ Green มีฟังก์ชันสี่จุด ฯลฯ เช่นเดียวกับสมการของ Bogolyubov ระบบนี้สามารถแก้ไขได้โดยการ "หัก" โซ่เท่านั้น (โดยปกติจะเลือกตำแหน่งของ "ตัวแตก" จากการพิจารณาทางกายภาพและกำหนดสิ่งที่ได้รับ)

ร.ส.อีกประเภทหนึ่ง ในทฤษฎีสนามควอนตัม - ฝูงชนมีตัวตนในทฤษฎี เขตข้อมูลเกจตัวตนเหล่านี้ยังเป็นตัวแทนของความสัมพันธ์แบบอินทิโกร-ดิฟเฟอเรนเชียลที่เชื่อมต่อฟังก์ชันของกรีนกับฟังก์ชันที่ต่างกัน จำนวนเส้นภายนอก p เป็นผลจากค่าไม่แปรเปลี่ยนเกจของทฤษฎี โดยมีบทบาทสำคัญในการตรวจสอบความสมมาตรของเกจในระหว่างขั้นตอน การฟื้นฟู

สุดท้ายนี้ ตัวโพรซีเดอร์เองก็เป็นโพรซีเดอร์ที่เกิดซ้ำเช่นกัน: ในแต่ละขั้นตอน (ในแต่ละลูปที่ตามมา) คู่สัญญาได้มาจากการคำนวณไดอะแกรมที่มีการวนซ้ำน้อยลง (ดูรายละเอียดเพิ่มเติมที่ การดำเนินการ R)อ. เอ็ม. มาโลคอสตอฟ

สารานุกรมกายภาพ. ใน 5 เล่ม - ม.: สารานุกรมโซเวียต. บรรณาธิการบริหาร A. M. Prokhorov. 1988 .

ดูว่า "ความสัมพันธ์ที่เกิดขึ้นซ้ำ" ในพจนานุกรมอื่น ๆ คืออะไร:

ความสัมพันธ์ที่เกิดซ้ำ- - [แอล.จี. ซูเมนโก พจนานุกรมภาษาอังกฤษเป็นภาษารัสเซียเกี่ยวกับเทคโนโลยีสารสนเทศ อ.: รัฐวิสาหกิจ TsNIIS, 2546.] หัวข้อเทคโนโลยีสารสนเทศในความสัมพันธ์ที่เกิดซ้ำของ EN ทั่วไป ... คู่มือนักแปลด้านเทคนิค

- (ฟังก์ชันเวเบอร์) ชื่อทั่วไปของฟังก์ชันพิเศษที่เป็นคำตอบของสมการเชิงอนุพันธ์ที่ได้จากการประยุกต์ใช้วิธีการแยกตัวแปรสำหรับสมการทางฟิสิกส์คณิตศาสตร์ เช่น สมการลาปลาซ สมการ ... ... Wikipedia

หรือการนับสัมผัสของโจเซฟัส ซึ่งเป็นปัญหาทางคณิตศาสตร์ที่มีชื่อเสียงพร้อมหวือหวาทางประวัติศาสตร์ ภารกิจนี้มีพื้นฐานมาจากตำนานที่ว่าการปลดประจำการของโจเซฟัสซึ่งปกป้องเมืองยอดฟัตไม่ต้องการยอมจำนนต่อกองกำลังที่เหนือกว่าของชาวโรมันที่ปิดกั้นถ้ำ.... ... วิกิพีเดีย

Pafnutiy Lvovich Chebyshev ในทางคณิตศาสตร์ ลำดับของพหุนามตั้งฉากคือลำดับอนันต์ของพหุนามจริง... Wikipedia

บทความนี้เสนอให้ลบ คำอธิบายเหตุผลและการสนทนาที่เกี่ยวข้องสามารถดูได้ที่หน้า Wikipedia: จะถูกลบ / 22 พฤศจิกายน 2555 ในขณะที่กระบวนการสนทนาคือ ... Wikipedia

ลำดับปาโดวันเป็นลำดับจำนวนเต็ม 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 ... วิกิพีเดีย

พหุนามเฮอร์ไมต์บางประเภทเป็นลำดับของพหุนามของตัวแปรจริงตัวหนึ่ง พหุนามของเฮอร์ไมต์เกิดขึ้นในทฤษฎีความน่าจะเป็น เชิงร่วม และฟิสิกส์ พหุนามเหล่านี้ตั้งชื่อตาม Charles Hermite สารบัญ 1... ...วิกิพีเดีย

- (ฟังก์ชัน Bessel) คำตอบ Zv(z) สมการ Bessel โดยที่พารามิเตอร์ (ดัชนี) v เป็นจำนวนจริงหรือจำนวนเชิงซ้อนตามอำเภอใจ ในการใช้งานมักพบสมการที่ขึ้นอยู่กับพารามิเตอร์สี่ตัว: คำตอบที่แสดงในรูปของ C... สารานุกรมทางกายภาพ

วิธีการแก้ระบบพีชคณิตเชิงเส้น สมการ A x = b ด้วยเมทริกซ์ที่ไม่เสื่อมของ Hermitian A ในบรรดาวิธีการโดยตรง วิธีนี้จะมีประสิทธิภาพมากที่สุดเมื่อนำมาใช้บนคอมพิวเตอร์ รูปแบบการคำนวณของวิธีนี้โดยทั่วไปจะขึ้นอยู่กับการแยกตัวประกอบของเฮอร์มิเทียน... ... สารานุกรมคณิตศาสตร์

ฟังก์ชัน Bessel แบบดัดแปลงคือฟังก์ชัน Bessel ของอาร์กิวเมนต์จินตภาพล้วนๆ หากเราแทนที่ด้วยสมการเชิงอนุพันธ์เบสเซลก็จะได้รูปแบบ สมการนี้เรียกว่าสมการเบสเซลที่ถูกดัดแปลง ... Wikipedia

ด้วยข้อมูลการสังเกตปริมาณมาก เอ็กซ์วิธีการอันจำกัดในการแก้สมการความน่าจะเป็นนำไปสู่ปัญหาในการคำนวณที่สำคัญซึ่งเกี่ยวข้องกับความจำเป็นในการจดจำข้อมูลเริ่มต้นจำนวนมากและผลลัพธ์การคำนวณขั้นกลาง ในเรื่องนี้ สิ่งที่น่าสนใจเป็นพิเศษคือวิธีการที่เกิดซ้ำซึ่งการประมาณความน่าจะเป็นสูงสุดจะถูกคำนวณเป็นขั้นตอนโดยมีความแม่นยำเพิ่มขึ้นทีละน้อย โดยแต่ละขั้นตอนจะเกี่ยวข้องกับการได้รับข้อมูลการสังเกตใหม่ และขั้นตอนการเกิดซ้ำจะถูกสร้างขึ้นในลักษณะที่จะเก็บไว้ในหน่วยความจำ จำนวนข้อมูลที่น้อยที่สุดที่เป็นไปได้จากขั้นตอนก่อนหน้า ข้อดีเพิ่มเติมและสำคัญมากจากมุมมองเชิงปฏิบัติของวิธีการเกิดซ้ำคือความพร้อมในการสร้างผลลัพธ์ในขั้นตอนกลางใดๆ

ซึ่งทำให้แนะนำให้ใช้วิธีที่เกิดซ้ำแม้ในกรณีที่เป็นไปได้ที่จะได้คำตอบที่แน่นอนของสมการความน่าจะเป็นสูงสุดโดยวิธีจำกัด และทำให้วิธีนี้มีคุณค่ามากยิ่งขึ้นเมื่อเป็นไปไม่ได้ที่จะหานิพจน์เชิงวิเคราะห์ที่แน่นอนสำหรับการประมาณค่าสูงสุด ความน่าจะเป็น

ให้ชุดข้อมูลการสังเกตเป็นลำดับเพื่ออธิบายว่าเวกเตอร์ใดที่เราแนะนำ (เช่นเคย แต่ละส่วนประกอบสามารถเป็นเวกเตอร์ ส่วนของกระบวนการสุ่ม เป็นต้น) อนุญาต เป็นฟังก์ชันความน่าจะเป็น, และ

ลอการิทึมของมัน ส่วนหลังสามารถแสดงอยู่ในแบบฟอร์มได้เสมอ

ลอการิทึมของฟังก์ชันความน่าจะเป็นสำหรับประชากรของข้อมูลการสังเกตที่ไม่มีค่าสุดท้าย และ

ลอการิทึมของความหนาแน่นของความน่าจะเป็นแบบมีเงื่อนไขของค่าสำหรับค่าที่กำหนดของ และ .

การเป็นตัวแทน (7.5.16) สำหรับลอการิทึมของฟังก์ชันความน่าจะเป็นเป็นพื้นฐานในการได้รับขั้นตอนที่เกิดซ้ำเพื่อคำนวณการประมาณความน่าจะเป็นสูงสุด ลองพิจารณากรณีปกติ ในกรณีนี้ สามารถหาค่าประมาณความน่าจะเป็นสูงสุดเพื่อใช้เป็นคำตอบของสมการได้

ซึ่งต่างจาก (7.1.6) เพียงแต่แนะนำดัชนีเท่านั้น พี วายลอการิทึมของฟังก์ชันความน่าจะเป็น

ให้เราแสดงคำตอบของสมการนี้โดยเน้นว่าค่าประมาณนี้ได้มาจากชุดข้อมูลเชิงสังเกต ในทำนองเดียวกัน ให้เราแสดงด้วยการแก้สมการประมาณความน่าจะเป็นสูงสุดที่ได้รับจากจำนวนรวมของข้อมูล

สมการ (7.5.19) สามารถเขียนใหม่ได้โดยคำนึงถึง (7.5.16) ในรูปแบบต่อไปนี้:

ให้เราขยายด้านซ้ายมือของ (7.5.20) ออกเป็นอนุกรม Taylor ในบริเวณใกล้จุดนั้น โดยที่

(7.5.22)

เวกเตอร์เกรเดียนต์ของฟังก์ชันที่จุด ; คำนี้จะกลายเป็นศูนย์เนื่องจากข้อเท็จจริงที่ว่า , เป็นวิธีแก้สมการความน่าจะเป็นสำหรับค่าก่อนหน้า (ป-ขั้นตอนที่ 1:

เมทริกซ์สมมาตรของอนุพันธ์อันดับสองของลอการิทึมของฟังก์ชันความน่าจะเป็นที่จุด เมื่อใช้เครื่องหมายตรงกันข้าม เงื่อนไขการขยายที่ไม่ได้เขียนไว้จะมีกำลังสองและลำดับขนาดเล็กที่สูงกว่าเมื่อเทียบกับความแตกต่าง หากละเลยสิ่งหลังเหล่านี้ เราจะได้คำตอบโดยประมาณต่อไปนี้สำหรับสมการความน่าจะเป็นสูงสุด:

เมทริกซ์ผกผันอยู่ที่ไหน

โซลูชันนี้นำเสนอในรูปแบบของความสัมพันธ์ที่เกิดซ้ำซึ่งกำหนดค่าถัดไปของการประมาณผ่านการประมาณการในขั้นตอนก่อนหน้าและการแก้ไข , ขึ้นอยู่กับข้อมูลการสังเกตที่มีอยู่โดยตรงและผ่านการประเมินครั้งก่อน การแก้ไขเกิดขึ้นเป็นผลคูณของการไล่ระดับสีของลอการิทึมของความหนาแน่นของความน่าจะเป็นแบบมีเงื่อนไขของค่าที่ได้รับใหม่ เอ็กซ์ n ณ จุดเท่ากับการประมาณครั้งก่อน ถึงเมทริกซ์น้ำหนัก . อย่างหลังถูกกำหนดโดยนิพจน์ (7.5.23) และยังขึ้นอยู่กับการประมาณค่าในขั้นตอนก่อนหน้า และการพึ่งพาข้อมูลการสังเกตใหม่ถูกกำหนดโดยรูปแบบของลอการิทึมของความหนาแน่นของความน่าจะเป็นแบบมีเงื่อนไข

รูปแบบของความสัมพันธ์ (7.5.24) คล้ายกับ (7.5.8) มาก ซึ่งใช้วิธีการวนซ้ำในการคำนวณค่าประมาณความน่าจะเป็นสูงสุดโดยใช้วิธีของนิวตัน อย่างไรก็ตามในความเป็นจริงแล้ว พวกเขามีความแตกต่างกันอย่างมาก ใน (7.5.8) การแก้ไขค่าประมาณก่อนหน้าถูกกำหนดโดยเกรเดียนต์ของลอการิทึมของฟังก์ชันความน่าจะเป็นทั้งหมด ซึ่งจะขึ้นอยู่กับข้อมูลการสังเกตที่มีอยู่ทั้งหมดเสมอ ซึ่งจำเป็นต้องจำทั้งเซตนี้ ตาม (7.5.24) การแก้ไขจะถูกกำหนดโดยขนาดของการไล่ระดับสี ซึ่งเนื่องจากคุณสมบัติของความหนาแน่นของความน่าจะเป็นแบบมีเงื่อนไข จริงๆ แล้วขึ้นอยู่กับค่าเหล่านั้น () ซึ่งมีความสัมพันธ์ทางสถิติที่แข็งแกร่งเท่านั้น กับ เอ็กซ์ n. ความแตกต่างนี้เป็นผลมาจากตัวเลือกพิเศษของการประมาณก่อนหน้าเป็นการประมาณความน่าจะเป็นสูงสุดที่พบจากชุดข้อมูลการสังเกตที่ลดลงหนึ่งค่า และเด่นชัดเป็นพิเศษสำหรับค่าอิสระของ () ในกรณีสุดท้ายนี้

เนื่องจากมันขึ้นอยู่กับและเท่านั้น เอ็กซ์ n และการไล่ระดับสีนั้นมาจากค่าประมาณก่อนหน้าเท่านั้นและค่าที่ได้รับใหม่เท่านั้น ป- mstep ของข้อมูลการสังเกต ดังนั้น เมื่อใช้ค่าอิสระในการสร้างเวกเตอร์ จึงไม่จำเป็นต้องจดจำข้อมูลอื่นใดจากขั้นตอนก่อนหน้า ยกเว้นค่าการประเมิน

ในทำนองเดียวกัน ในกรณีของลำดับมาร์คอฟของข้อมูลการสังเกต นั่นคือ เมื่อใด

เวกเตอร์ขึ้นอยู่กับค่าปัจจุบันและหนึ่งค่าก่อนหน้าเท่านั้น ในกรณีนี้ สำหรับการคำนวณ จำเป็นต้องจดจำจากขั้นตอนก่อนหน้า นอกเหนือจากค่าแล้ว เฉพาะค่า แต่ไม่ใช่ชุดข้อมูลการสังเกตทั้งหมด เช่นเดียวกับในขั้นตอนวนซ้ำ โดยทั่วไปการคำนวณอาจต้องจัดเก็บค่าก่อนหน้าจำนวนมากขึ้น () อย่างไรก็ตามเนื่องจากจำเป็นต้องคำนึงถึงเฉพาะค่าที่ขึ้นอยู่กับทางสถิติเท่านั้น ตัวเลขนี้จึงน้อยกว่าปริมาตรรวมเกือบทุกครั้ง ของข้อมูลการสังเกต ดังนั้น หากเวกเตอร์อธิบายลำดับเวลา จำนวนสมาชิกของลำดับนี้ที่จะจดจำจะถูกกำหนดตามเวลาที่สัมพันธ์กัน และสัดส่วนสัมพัทธ์ของพวกมันจะลดลงในสัดส่วนผกผัน nเช่นเดียวกับในกรณีของค่าอิสระ

ให้เราพิจารณาโครงสร้างของเมทริกซ์น้ำหนักที่รวมอยู่ในความสัมพันธ์การเกิดซ้ำ (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) มีคุณสมบัติการลู่เข้าที่คล้ายกันภายใต้สภาวะทั่วไปมากกว่า ถ้าลำดับเป็นแบบ Ergodic

วิธีที่สองที่กล่าวถึงนั้นขึ้นอยู่กับการแทนที่เมทริกซ์ของอนุพันธ์อันดับสองของลอการิทึมของฟังก์ชันความน่าจะเป็นด้วยความคาดหวังทางคณิตศาสตร์ - เมทริกซ์ข้อมูลฟิชเชอร์ซึ่งสามารถเขียนได้เมื่อคำนึงถึง (7.5.16) เป็น:

โดยที่คล้ายกับ (7.5.26)

การแทนที่เมทริกซ์ใน (7.5.24) ด้วยเมทริกซ์ เราจะได้ความสัมพันธ์การเกิดซ้ำ

สำหรับการคำนวณโดยประมาณของการประมาณความน่าจะเป็นสูงสุดที่เสนอโดย Sakrison (ในต้นฉบับสำหรับการกระจายที่เหมือนกันอย่างอิสระ เมื่อ และ . ความสัมพันธ์การเกิดซ้ำนี้ง่ายกว่าระบบ (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) สำหรับค่าต่างๆ ของ || เพื่อให้บรรลุโดยใช้ขั้นตอนที่เกิดซ้ำ ค่าสูงสุดทั่วโลกของฟังก์ชันนี้ ณ จุดที่สอดคล้องกับค่าที่แท้จริงของพารามิเตอร์

โดยลำดับของการเพิ่มขึ้นในช่วงเวลาที่สองของอนุพันธ์ของลอการิทึมของฟังก์ชันความน่าจะเป็นสำหรับค่าสัมบูรณ์ที่มีขนาดใหญ่ ข้อกำหนดเหล่านี้เป็นผลมาจากเงื่อนไขทั่วไปมากขึ้นสำหรับการลู่เข้าไปยังจุดของส่วนประกอบทั้งหมดหรือบางส่วนของกระบวนการสุ่มมาร์คอฟ ซึ่งกระบวนการเกิดซ้ำอย่างใดอย่างหนึ่งนำไปสู่

โดยสรุป เรายังสังเกตด้วยว่าในกรณีที่มีวิธีแก้สมการความน่าจะเป็นสูงสุดที่แน่นอน สมการนี้สามารถแสดงในรูปแบบที่เกิดซ้ำได้เกือบทุกครั้ง ให้เรายกตัวอย่างง่ายๆ สองตัวอย่างที่ไม่เหมือนกัน ดังนั้น การประมาณเบื้องต้นของความคาดหวังทางคณิตศาสตร์ที่ไม่ทราบของตัวแปรสุ่มปกติในประชากร nค่าตัวอย่างในรูปแบบของค่าเฉลี่ยเลขคณิต

เป็นการประมาณความน่าจะเป็นสูงสุดและสามารถแสดงในรูปแบบที่เกิดซ้ำได้:

ซึ่งเป็นกรณีพิเศษที่ง่ายที่สุด (7.5.30) ด้วย

อีกตัวอย่างหนึ่งคือการประมาณค่าความน่าจะเป็นสูงสุดที่ผิดปกติสำหรับพารามิเตอร์ - ความกว้างของการแจกแจงแบบสี่เหลี่ยม - จาก (7.4.2) ซึ่งสามารถกำหนดได้จากความสัมพันธ์ที่เกิดซ้ำ

ด้วยเงื่อนไขเบื้องต้น ความสัมพันธ์การเกิดซ้ำนี้เป็นประเภทอื่น: ทางด้านขวามือไม่สามารถแสดงเป็นผลรวมของการประมาณการครั้งก่อนและการแก้ไขเล็กน้อย ซึ่งเป็นผลมาจากความผิดปกติของตัวอย่างนี้ อย่างไรก็ตาม มีข้อดีทั้งหมดของวิธีการเกิดซ้ำ โดยต้องจำตัวเลขเพียงตัวเดียวจากขั้นตอนก่อนหน้า นั่นคือค่าประมาณ และลดการค้นหาลงเหลือเพียงการเปรียบเทียบเดียว แทนที่จะเปรียบเทียบค่าทั้งหมด

ตัวอย่างที่ให้มาแสดงให้เห็นถึงข้อดีของวิธีการเกิดซ้ำแม้ในกรณีที่สมการความน่าจะเป็นสูงสุดช่วยให้สามารถหาคำตอบได้อย่างแม่นยำ เนื่องจากความเรียบง่ายในการแสดงผลลัพธ์เชิงวิเคราะห์ไม่เหมือนกันกับความเรียบง่ายในการคำนวณเมื่อได้ผลลัพธ์มา

7.5.3. การเปลี่ยนไปสู่เวลาต่อเนื่อง สมการเชิงอนุพันธ์สำหรับตัวประมาณความน่าจะเป็นสูงสุด

ให้เราพิจารณาเป็นกรณีพิเศษเมื่อมีข้อมูลการสังเกตที่มีอยู่ เอ็กซ์ไม่ได้อธิบายด้วยชุดจุดตัวอย่าง , เป็นตัวแทนของส่วนหนึ่งของการดำเนินการตามกระบวนการบางอย่าง , ขึ้นอยู่กับพารามิเตอร์ที่ระบุในช่วงเวลา , และความยาวของช่วงเวลานี้อาจเพิ่มขึ้นในระหว่างการสังเกต (จุดเวลา ทีเป็นตัวแปร)

สำหรับคำอธิบายทางสถิติของข้อมูลการสังเกต ในกรณีนี้ มีการแนะนำฟังก์ชันอัตราส่วนความน่าจะเป็น ซึ่งเป็นขีดจำกัดที่ สูงสุดของอัตราส่วนของการแจกแจงความหนาแน่นของความน่าจะเป็นของชุดของค่าที่ค่าที่กำหนดโดยพลการกับความน่าจะเป็นที่คล้ายกัน ความหนาแน่นที่ค่าคงที่ที่แน่นอนและในบางกรณีเมื่อมันอนุญาตให้เป็นตัวแทนของ โดยที่ กระบวนการสุ่ม เป็นอิสระจาก ความหนาแน่นของความน่าจะเป็นของชุดของค่าที่มีให้นั้น การใช้ฟังก์ชันอัตราส่วนความน่าจะเป็นช่วยให้เราขจัดปัญหาอย่างเป็นทางการในการกำหนดความหนาแน่นของความน่าจะเป็นที่เกิดขึ้นเมื่อเคลื่อนที่ไปยังเวลาที่ต่อเนื่องกัน

ลอการิทึมของฟังก์ชันอัตราส่วนความน่าจะเป็นสามารถแสดงเป็นได้

โดยที่การทำงานของกระบวนการบางอย่างในช่วงเวลานั้น ในบางกรณี ฟังก์ชันจะเสื่อมลงเป็นฟังก์ชันที่ขึ้นอยู่กับค่าของ . ถ้าอย่างนั้น

โดยที่คือฟังก์ชันที่ทราบของเวลาและพารามิเตอร์ และเป็นกระบวนการสุ่มที่สัมพันธ์กันแบบเดลต้า (“สัญญาณรบกวนสีขาว”) พร้อมความหนาแน่นของสเปกตรัม เอ็น o จากนั้น เลือกอัตราส่วนความน่าจะเป็นของการแจกแจงความน่าจะเป็นเป็นตัวส่วน เอ็กซ์ที่ เราจะมี

อนุญาต การประมาณความน่าจะเป็นสูงสุดของพารามิเตอร์ที่สร้างขึ้นจากการดำเนินการตามกระบวนการในช่วงเวลานั่นคือการแก้สมการความน่าจะเป็นสูงสุด

เราได้รับความแตกต่างทางด้านซ้ายของสมการนี้ตามเวลา

แนะนำการกำหนด

และการแก้สมการ (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) ของประเภท Riccati

กลับ