ในทางคณิตศาสตร์ วิธี การเดินบนทรงกลม (WoS)เป็นอัลกอริ ทึมเชิงความน่าจะเป็นเชิงตัวเลข หรือวิธีการมอนเตคาร์โลซึ่งใช้เป็นหลักในการประมาณคำตอบของปัญหาค่าขอบเขต เฉพาะบางอย่าง สำหรับสมการเชิงอนุพันธ์ย่อย (PDEs) ^{[ 1 ] [ 2 ]}วิธีการ WoS ได้รับการแนะนำครั้งแรกโดยMervin E. Mullerในปี 1956 เพื่อแก้สมการลาปลาส [ ^{1 ] และ}ตั้งแต่นั้นมาก็ได้รับการขยายไปสู่ปัญหาอื่นๆ

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

ให้เป็นโดเมน ที่มีขอบเขต ในโดยมีขอบเขตที่สม่ำเสมอเพียงพอให้hเป็นฟังก์ชันบนและให้เป็นจุดภายใน${\displaystyle \Omega }$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle \Gamma }$${\displaystyle \Gamma }$${\displaystyle x}$${\displaystyle \Omega }$

พิจารณาปัญหา Dirichlet :

${\displaystyle {\begin{cases}\Delta u(x)=0&{\mbox{if }}x\in \Omega \\u(x)=h(x)&{\mbox{if }}x\in \Gamma .\end{cases}}}$

สามารถแสดงได้อย่างง่ายดาย^{[ a ]}ว่าเมื่อมีคำตอบอยู่ สำหรับ:${\displaystyle u}$${\displaystyle x\in \Omega }$

${\displaystyle u(x)=\mathbb {E} _{x}[h(W_{\tau })]}$

โดยที่Wคือกระบวนการ Wienerมิติdค่าที่คาดหวังจะพิจารณาแบบมีเงื่อนไขบน{ W = x }และτคือเวลาออกครั้งแรกจากΩ

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

${\displaystyle \mathbb {E} _{x}[h(W_{\tau })]\sim {\frac {1}{n}}\sum _{i=1}^{n}h(W_{\tau }^{i})}$

วิธี WoS ให้วิธีการที่มีประสิทธิภาพในการสุ่มตัวอย่างจุดออกแรกของการเคลื่อนที่แบบบราวน์จากโดเมน โดยสังเกตว่าสำหรับ ทรงกลม ( d  −  1) ใดๆ ที่มีจุดศูนย์กลางอยู่ที่xจุดออกแรกของWจากทรงกลมจะมีการกระจายอย่างสม่ำเสมอทั่วพื้นผิว ดังนั้นจึงเริ่มต้นด้วยx ^{( 0 )}เท่ากับxและวาดทรงกลมที่ใหญ่ที่สุดที่มีจุดศูนย์กลางอยู่ที่x ^{( 0 )}และอยู่ภายในโดเมน จุดออกแรกx ^{( 1 )}จากจะกระจายอย่างสม่ำเสมอทั่วพื้นผิว โดยการทำซ้ำขั้นตอนนี้แบบอุปนัย WoS จะให้ลำดับ( x ^{( n )} )ของตำแหน่งของการเคลื่อนที่แบบบราวน์${\displaystyle {\mathcal {S}}_{0}}$${\displaystyle {\mathcal {S}}_{0}}$

ตามสัญชาตญาณ กระบวนการจะลู่เข้าสู่จุดออกแรกของโดเมน อย่างไรก็ตาม อัลกอริทึมนี้ใช้ขั้นตอนจำนวนอนันต์เกือบจะแน่นอนในการสิ้นสุด สำหรับการนำไปใช้ในการคำนวณ กระบวนการมักจะหยุดเมื่อเข้าใกล้ขอบเขตมากพอ และส่งคืนการฉายภาพของกระบวนการบนขอบเขต ขั้นตอนนี้บางครั้งเรียกว่าการแนะนำ-shell หรือ-layer ^{[ 4 ]}${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$

เลือก. โดยใช้สัญลักษณ์เดียวกันกับข้างต้น อัลกอริทึมการเดินบนทรงกลมสามารถอธิบายได้ดังนี้:${\displaystyle \varepsilon >0}$

1. เริ่มต้น :${\displaystyle x^{(0)}=x}$
2. ในขณะที่: ${\displaystyle d(x^{(n)},\Gamma )>\varepsilon }$
   1. ชุด.${\displaystyle r_{n}=d(x^{(n)},\Gamma )}$
   2. สุ่มเลือกเวกเตอร์ที่มีการกระจายอย่างสม่ำเสมอทั่วทรงกลมหน่วย โดยไม่ขึ้นกับเวกเตอร์ก่อนหน้า${\displaystyle \gamma _{n}}$
   3. ชุด${\displaystyle x^{(n+1)}:=x^{(n)}+r_{n}\gamma _{n}}$
3. เมื่อไร:${\displaystyle d(x^{(n)},\Gamma )\leq \varepsilon }$
4. ${\displaystyle x_{f}:=p_{\Gamma }(x^{(n)})}$การฉายภาพเชิงตั้งฉากของบน${\displaystyle x^{(n)}}$${\displaystyle \Gamma }$
5. กลับ${\displaystyle x_{f}}$

ผลลัพธ์ที่ได้คือตัวประมาณจุดออกแรกของกระบวนการ Wiener ที่เริ่มต้นจากจุดในแง่ที่ว่าจุดทั้งสองมีฟังก์ชันการกระจายความน่าจะเป็นที่ใกล้เคียงกัน (ดูรายละเอียดเกี่ยวกับข้อผิดพลาดด้านล่าง)${\displaystyle x_{f}}$${\displaystyle \Omega }$${\displaystyle x}$

วิธีการนี้ได้รับการศึกษา พัฒนา และปรับปรุงอย่างกว้างขวาง ตัวอย่างเช่น ปัจจุบันมีการนำไปใช้อย่างแพร่หลายในการคำนวณคุณสมบัติทางกายภาพของวัสดุ (เช่นความจุไฟฟ้าพลังงานภายในไฟฟ้าสถิตของโมเลกุล เป็นต้น) ส่วนขยายที่น่าสนใจบางประการ ได้แก่:

• สูตรเฟย์นแมน-แคค
• กระบวนการสุ่มและปัญหาค่าขอบเขต
• วิธีออยเลอร์-มารุยามะสำหรับการสุ่มตัวอย่างเส้นทางของกระบวนการแพร่ทั่วไป

• Sabelfeld, Karl K. (1991). วิธีมอนเตคาร์โลในปัญหาค่าขอบเขตเบอร์ลิน [ฯลฯ]: Springer-Verlag. ISBN 9783540530015.

• วิธีการมอนเตคาร์โลแบบต่อเนื่องบางวิธีสำหรับปัญหา Dirichletบทความที่ Marvin Edgar Muller นำเสนอวิธีการนี้
• การเคลื่อนที่แบบบราวน์โดย ปีเตอร์ มอร์เตอร์ส และ ยูวัล เปเรส ดูบทที่ 3.3 เกี่ยวกับการวัดแบบฮาร์มอนิก ฟังก์ชันกรีน และจุดออก