ในทางคณิตศาสตร์ระบบฟังก์ชันแบบวนซ้ำ ( IFS ) เป็นวิธีการสร้างแฟรกทัลโดยแฟรกทัลที่ได้มักจะมีความคล้ายคลึงกันในตัวเอง แฟรก ทัล IFS มีความเกี่ยวข้องกับทฤษฎีเซตมากกว่าเรขาคณิตแฟรกทัล^{[ 1 ]}ได้มีการนำเสนอในปี 1981

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

ในทางรูปแบบ ระบบ ฟังก์ชันที่ทำซ้ำคือเซตจำกัดของ การแม ปการหดตัวบนปริภูมิเมตริกที่สมบูรณ์^{[ 2 ]}ในเชิงสัญลักษณ์

${\displaystyle \{f_{i}:X\to X\mid i=1,2,\dots ,N\},\ N\in \mathbb {N} }$

ระบบฟังก์ชันแบบวนซ้ำก็คือระบบฟังก์ชัน f _iแต่ละฟังก์ชัน เป็นการหดตัวบนปริภูมิเมตริกสมบูรณ์X

ฮัทชินสันแสดงให้เห็นว่าสำหรับปริภูมิเมตริกℝ ⁿหรือโดยทั่วไปสำหรับปริภูมิเมตริกที่สมบูรณ์ระบบฟังก์ชันดังกล่าวมี เซตคงที่ S ที่ไม่ว่างเปล่า และกระชับ (ปิดและมีขอบเขต) ที่ไม่ซ้ำกัน ^{[ 3 ]}วิธีหนึ่งในการสร้างเซตคงที่คือการเริ่มต้นด้วยเซตปิดและมีขอบเขตที่ไม่ว่างเปล่าเริ่มต้นS ₀และทำซ้ำการกระทำของf _iโดยให้S _{n +1}เป็นการรวมกันของภาพของS _nภายใต้f _iจากนั้นให้Sเป็นการปิดของลิมิต${\displaystyle X}$ลิมn →∞S _n . ในเชิงสัญลักษณ์ เซตคงที่ (ไม่ว่างเปล่าและเป็นเซตกระชับ) ที่ไม่ซ้ำกันเพียงหนึ่งเดียว S ⊆ Xมีคุณสมบัติดังนี้

${\displaystyle S={\overline {\bigcup _{i=1}^{N}f_{i}(S)}}.}$

ดังนั้น เซตSจึงเป็นเซตคงที่ของตัวดำเนินการฮัทชินสันF  : 2 ^X → 2 ^Xซึ่งกำหนดไว้สำหรับA ⊆ Xผ่านทาง

${\displaystyle F(A)={\overline {\bigcup _{i=1}^{N}f_{i}(A)}}.}$

การมีอยู่และความเป็นเอกลักษณ์ของSเป็นผลมาจากหลักการของการแมปแบบหดตัวเช่นเดียวกับข้อเท็จจริงที่ว่า

${\displaystyle \lim _{n\to \infty }F^{n}(A)=S}$

สำหรับเซตกระชับA ใดๆ ที่ไม่ว่างเปล่า ในX (สำหรับ IFS แบบหดตัว การลู่เข้านี้เกิดขึ้นแม้กระทั่งสำหรับเซตปิดที่มีขอบเขตA ใดๆ ที่ไม่ว่างเปล่า ) สามารถสร้างองค์ประกอบสุ่มที่อยู่ใกล้กับS ได้อย่างไม่จำกัด โดยใช้ "เกมแห่งความโกลาหล" ซึ่งจะอธิบายต่อไป

เมื่อเร็วๆ นี้ มีการแสดงให้เห็นว่า IFS ประเภทที่ไม่หดตัว (กล่าวคือ ประกอบด้วยแผนที่ที่ไม่ใช่การหดตัวเมื่อเทียบกับเมตริกที่เทียบเท่าทางโทโพโลยีใดๆ ในX ) สามารถสร้างตัวดึงดูดได้ สิ่งเหล่านี้เกิดขึ้นตามธรรมชาติในปริภูมิเชิงโปรเจกทีฟ แม้ว่าการหมุนแบบอตรรกยะคลาสสิกบนวงกลมก็สามารถปรับใช้ได้เช่นกัน^{[ 4 ]}

กลุ่มของฟังก์ชันf _iสร้างโมโนอิดภายใต้การประกอบฟังก์ชันถ้ามีฟังก์ชันดังกล่าวเพียงสองฟังก์ชัน โมโนอิดสามารถมองเห็นได้ในรูปของต้นไม้ไบนารีโดยที่แต่ละโหนดของต้นไม้สามารถประกอบฟังก์ชันกับฟังก์ชันใดฟังก์ชันหนึ่งได้ ( เช่นเลือกกิ่งซ้ายหรือกิ่งขวา) โดยทั่วไป ถ้ามี ฟังก์ชัน kฟังก์ชัน สามารถมองเห็นโมโนอิดได้ในรูปของต้นไม้k -ary เต็มรูปแบบ หรือที่เรียกว่าต้นไม้เคย์ลีย์

บางครั้งฟังก์ชัน f _iแต่ละฟังก์ชันจะต้องเป็นการ แปลง เชิงเส้นหรือโดยทั่วไปแล้วเป็นการแปลงแบบแอฟฟินและดังนั้นจึงแสดงด้วยเมทริกซ์อย่างไรก็ตาม IFS อาจสร้างขึ้นจากฟังก์ชันที่ไม่เป็นเชิงเส้นได้เช่นกัน รวมถึงการแปลงแบบโปรเจคทีฟและการแปลงแบบโมเบียสเปลวไฟแฟรกทัลเป็นตัวอย่างของ IFS ที่มีฟังก์ชันที่ไม่เป็น เชิงเส้น

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

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

แม้ว่าทฤษฎีของ IFS จะกำหนดให้แต่ละฟังก์ชันต้องหดตัว แต่ในทางปฏิบัติซอฟต์แวร์ที่ใช้ IFS นั้นต้องการเพียงแค่ให้ทั้งระบบหดตัวโดยเฉลี่ยเท่านั้น^{[ 5 ]}

PIFS (partitioned iterated function systems) หรือเรียกอีกอย่างว่า local iterated function systems ^{[ 6 ]}ให้การบีบอัดภาพที่ดีอย่างน่าประหลาดใจ แม้แต่ภาพถ่ายที่ดูเหมือนจะไม่มีโครงสร้างที่คล้ายคลึงกันแบบที่แสดงโดยแฟรกทัล IFS แบบง่ายๆ^{[ 7 ]}

มีอัลกอริธึมที่รวดเร็วมากในการสร้างภาพจากชุดพารามิเตอร์ IFS หรือ PIFS ซึ่งเร็วกว่าและใช้พื้นที่จัดเก็บน้อยกว่ามากในการจัดเก็บคำอธิบายวิธีการสร้าง ส่งคำอธิบายนั้นไปยังอุปกรณ์ปลายทาง และสร้างภาพนั้นขึ้นใหม่บนอุปกรณ์ปลายทาง เมื่อเทียบกับการจัดเก็บและส่งสีของแต่ละพิกเซลในภาพ^{[ 6 ]}

ปัญหาผกผันนั้นยากกว่า: เมื่อกำหนดภาพดิจิทัลต้นฉบับใดๆ เช่น ภาพถ่ายดิจิทัล ให้พยายามหาชุดพารามิเตอร์ IFS ซึ่งเมื่อประเมินโดยการวนซ้ำ จะสร้างภาพอื่นที่คล้ายกับภาพต้นฉบับ ในปี 1989 Arnaud Jacquin ได้นำเสนอวิธีแก้ปัญหาผกผันในรูปแบบที่จำกัดโดยใช้ PIFS เท่านั้น รูปแบบทั่วไปของปัญหาผกผันยังคงไม่ได้รับการแก้ไข^{[ 8 ] [ 9 ] [ 6 ]}

ภายในปี พ.ศ. 2538 ซอฟต์แวร์ การบีบอัดแฟรกทัล ทั้งหมด ใช้แนวทางของ Jacquin ^{[ 9 ]}

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

ตัวอย่างแรกๆ ของแฟร็กทัลที่อาจสร้างขึ้นโดย IFS ได้แก่เซตแคนเตอร์ซึ่งได้รับการอธิบายครั้งแรกในปี 1884 และเส้นโค้งเดอแรมซึ่งเป็นเส้นโค้งคล้ายตนเองชนิดหนึ่งที่จอร์จ เดอแรม อธิบายไว้ ในปี 1957

IFS ได้รับการคิดค้นในรูปแบบปัจจุบันโดยJohn E. Hutchinsonในปี 1981 ^{[ 3 ]}และได้รับความนิยมจาก หนังสือ Fractals Everywhereของ Michael Barnsley

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

• ระบบฐานเชิงซ้อน
• ทฤษฎีคอลลาจ
• การประกอบฟังก์ชันวิเคราะห์แบบอนันต์
• ระบบ L
• การบีบอัดแบบแฟรกทัล

• คู่มือเบื้องต้นเกี่ยวกับทฤษฎีพื้นฐานของการประกอบฟังก์ชันเชิงซ้อนแบบอนันต์