PAGE 1 ,19(56( .,1(0$7,& $1$/<6,6 2) 52%27 0$1,38/$7256 %\ 5$&+,' 0$16(85 $ ',66(57$7,21 35(6(17(' 72 7+( *5$'8$7( 6&+22/ 2) 7+( 81,9(56,7< 2) )/25,'$ ,1 3$57,$/ )8/),//0(17 2) 7+( 5(48,5(0(176 )25 7+( '(*5(( 2) '2&725 2) 3+,/2623+< 81,9(56,7< 2) )/25,'$ PAGE 2 7R WKRVH ZKR IRXJKW IRU WKH IUHHGRP DQG HGXFDWLRQ RI DOO $OJHULDQV PAGE 3 $&.12:/('*0(176 7KLV ZRUN ZRXOG QRW KDYH EHHQ SRVVLEOH ZLWKRXW WKH WHDFKLQJV WKH FRQVWDQW JXLGDQFH DQG WKH H[SHUW DGYLFH UHFHLYHG IURP P\ DGYLVRU 3URIHVVRU .HLWK / 'RW\ DP HVSHFLDOO\ JUDWHIXO IRU KLV HQFRXUDJHPHQWV KLV HQWKXVLDVP KLV JUHDW VHQVH RI KXPRU DQG KLV IULHQGOLQHVV ZKLFK PDGH WKLV ZRUN VR HQMR\DEOH ZRXOG OLNH WR WKDQN 'U +HUPDQ /DP 'U *HUKDUG ; 5LWWHU 'U 5DOSK 6HOIULGJH DQG 'U -RVH & 3ULQFLSH IRU WKHLU H[FHOOHQW VHUYLFH RQ P\ ILQDO FRPPLWWHH 7KDQNV DUH DOVR GXH WR 'U *LXVHSSH %DVLOH DQG 'U (JLQKDUG 0XWK IRU WKHLU SUHYLRXV VHUYLFH RQ P\ FRPPLWWHH DOVR ZLVK WR H[SUHVV P\ DSSUHFLDWLRQ WR 'U &DUO &UDQH ,,, IRU KLV KHOS ZLWK WKH FRPSXWHU JUDSKLFV VLPXODWLRQV DQG WKH SKRWRJUDSKV RI )LJXUH RI WKLV WH[W DQG WR 'U -RVHSK 'XII\ IRU WDNLQJ WKH WLPH WR DQVZHU P\ TXHVWLRQV 7KH ILQDQFLDO VXSSRUW UHFHLYHG WKURXJKRXW P\ GRFWRUDO VWXGLHV IURP WKH 0DWKHPDWLFV 'HSDUWPHQW DQG IURP WKH (OHFWULFDO (QJLQHHULQJ 'HSDUWPHQW RI WKH 8QLYHUVLW\ RI )ORULGD LQ WKH IRUP RI WHDFKLQJ DVVLVWDQWVKLSV LV JUDFHIXOO\ DFNQRZOHJHG 6SHFLDO WKDQNV DUH GXH WR LLL PAGE 4 'U 3H\WRQ = 3HHEOHV DQG WR 'U 5REHUW / 6XOOLYDQ IRU WKHLU WLPHO\ KHOS DQG XQGHUVWDQGLQJ ZRXOG OLNH WR WDNH WKLV RSSRUWXQLW\ WR WKDQN 0V *UHWD 6EURFR IRU EHLQJ VXFK D JUHDW JUDGXDWH VHFWUHWDU\ IRU FDULQJ DQG IRU KHU FRQVWDQW HQFRXUDJHPHQWV $OO WKH VWXGHQWV RI WKH 0DFKLQH ,QWHOOLJHQFH /DERUDWRU\ DOVR GHVHUYH UHFRJQLWLRQ IRU FUHDWLQJ VXFK D IULHQGO\ DQG SURGXFWLYH ZRUNLQJ HQYLURQPHQW ,Q SDUWLFXODU ZRXOG OLNH WR WKDQN 'U 6XEELDQ *RYLQGDUDM DQG 0U 'DYLG $OGHUPDQ IRU WKHLU KHOS LQ WKH ODERUDWRU\ ZRXOG DOVR OLNH WR H[SUHVV P\ JUDWLWXGH DQG P\ ORYH WR P\ IDPLO\ VSHFLDOO\ P\ SDUHQWV 2PDU $PRNUDQH 0DQVHXU DQG 'KLD X[ [X\ LV H[SUHVVHG LQ IUDPH )A LWV H[SUHVVLRQ ZLWK UHVSHFW WR IUDPH )ABO[ X VDWLVILHV LLX ; &L 6LUL 6LDL DL&L OX; LBOX\ 6L &L7L &LDL DL6L r+ Lf] Ds 7/ Gs [X] O RU LQ D FRPSDFW QRWDWLRQ L X L X f ZKHUH U A FRV DAf DMB VLQDef &A FRV Af DQG 6A VLQkAf DQG $A LV WKH KRPRJHQHRXV IUDPHWUDQVIRUP PDWUL[ 3DXO f 7KH OHDGLQJ VXSHUVFULSW LQGLFDWHV WKH IUDPH RI H[SUHVVLRQ 7KH KRPRJHQHRXV PDWUL[ WUDQVIRUP PHUHO\ H[SUHVVHV WKH IDFW WKDW IUDPH )A FDQ EH REWDLQHG IURP IUDPH )AA E\ WKH IROORZLQJ VHTXHQFH RI EDVLF WUDQVIRUPV 5RWDWLRQ DERXW RI DQJOH M ZKRVH KRPRJHQHRXV PDWUL[ LV PAGE 16 5]Lf &L 6L 6MB &L f 7UDQVODWLRQ RI F/ XQLWV DORQJ D[LV GHVFULEHG E\ WKH PDWUL[ 7U]GLf R R O GM f 7UDQVODWLRQ RI DA XQLWV DORQJ D[LV [A ZLWK KRPRJHQHRXV WUDQVIRUP 7U[DLf D f 5RWDWLRQ DERXW ;MB RI DQJOH 5[DLf UL DL R &7L I/ f 7KH PDWUL[ RI (T f LV REWDLQHG E\ WKH SURGXFW 3DXO f f n PAGE 17 $L 5]kLf 7U] GLf 7U[DA 5[8Lf $ XVHIXO GHFRPSRVLWLRQ RI PDWUL[ $L LV $L $L %L f ZLWK WKH GHILQLWLRQV $L 5]Lf DQG f %L 7U]GLf 7U[DLf 5ARAf f ([SOLFLWO\ PDWUL[ %L LV %L 7L &7L DL UL GL f ZKHUH *L LV WKH XSSHU OHIW [ LQ %L DQG NL LV WKH XSSHU ULJKW [ YHFWRU RI %Lr 7KH XSSHU OHIW [ PDWUL[ LQ $L LV WKH URWDWLRQ PDWUL[ 5L QHFHVVDU\ WR DOLJQ WKH XQLW YHFWRUV RI )L ZLWK WKHLU FRXQWHUSDUWV LQ )LB ZKLOH YHFWRU L DLFL DLVL SRVLWLRQV WKH RULJLQ RI )L ZLWK UHVSHFW WR )LBL PAGE 18 $ FRPSDFW DQG XVHIXO H[SUHVVLRQ IRU $A LV f 5RWDWLRQ PDWULFHV DUH RUWKRJRQDO VR 5A 5A7 ZKHUH WKH VXSHUVFULSW 7 GHQRWHV WKH WUDQVSRVH RSHUDWLRQ DQG WKH LQYHUVH RI PDWUL[ $A FDQ EH H[SUHVVHG DV FL 6L DL VLUL &LUL DL fDLGL VLDL &L&7L 7L ULGL 5L7 5L7OLf f 3UREOHP 'HILQLWLRQ ,I WKH RULHQWDWLRQ RI WKH HQGHIIHFWRU LV VSHFLILHG E\ WKH URWDWLRQ PDWUL[ 5 QHFHVVDU\ WR DOLJQ WKH XQLW YHFWRUV RI WKH HQGHIIHFWRU IUDPH )Q ZLWK WKH FRUUHVSRQGLQJ YHFWRUV RI EDVH IUDPH )J DQG WKH SRVLWLRQ RI WKH RULJLQ RI WKH HQG HIIHFWRU IUDPH LV JLYHQ DV D YHFWRU S ZLWK UHVSHFW WR WKH EDVH IUDPH )4 WKHQ WKH HQGHIIHFWRU SRVH LV DGHTXDWHO\ GHVFULEHG E\ WKH [ PDWUL[ Q[ E[ IF[ Q\ E\ E\ 3[ 3\ Q E W S 5 S Q] 3] PAGE 19 ZKHUH Q[ E[ IF[ 3[ Q Q\ E E\ W IF\ I S 3\ B Q] E] E] 3= DQG 5 Q[ E[ Q\ E\ Q] E] W W W ; \ ] 7KH LQYHUVH NLQHPDWLFV SUREOHP IRU D QGHJUHHRI IUHHGRP PDQLSXODWRU FRQVLVWV RI ILQGLQJ D VHW RI MRLQW YDULDEOHV YDOXHV FDOOHG D VROXWLRQ VHW WKDW ZLOO VDWLVI\ WKH HTXDWLRQ $ $ $ $ $rrr$Q 3 f 7KLV PDWUL[ HTXDWLRQ JLYHV ULVH WR D V\VWHP RI QRQOLQHDU HTXDWLRQV ZKRVH FRPSOH[LW\ GHSHQGV RQ WKH PDQLSXODWRU JHRPHWU\ DV GHVFULEHG E\ WKH '+SDUDPHWHUV $W OHDVW VL[ GHJUHHV RI IUHHGRP DUH UHTXLUHG WR DUELWUDULO\ SRVLWLRQ DQG RULHQW D ULJLG ERG\ LQ VSDFH 7KHUHIRUH ZKHQ Q LV ODUJHU WKDQ VL[ WKH PDQLSXODWRU LV UHGXQGDQW DQG WKH V\VWHP RI HTXDWLRQV LPSOLHG E\ (T f LV XQGHUFRQVWUDLQHG ,I Q LV OHVV WKDQ WKH V\VWHP EHFRPHV RYHUFRQVWUDLQHG DQG ZKHQ Q LV HTXDO WR WKH LQYHUVH NLQHPDWLF SUREOHP LV H[DFWO\ VSHFLILHG ,Q WKLV PAGE 20 UHVHDUFK ZH ZLOO DGGUHVV WKH LQYHUVH NLQHPDWLFV SUREOHP RI QRQUHGXQGDQW URERW PDQLSXODWRUV 0RVW H[LVWLQJ LQGXVWULDO PDQLSXODWRUV DUH RU GHJUHHRIIUHHGRP URERWV KHQFH LW LV RI SUDFWLFDO LPSRUWDQFH WR VROYH (T f IRU Q DQG Q 7KH QXPHULFDO WHFKQLTXHV GHYHORSHG LQ WKLV WH[W DUH EDVHG RQ D FRPSOHWH LQYHUVH NLQHPDWLF DQDO\VLV RI IRXUGHJUHHRI IUHHGRP PDQLSXODWRUV 7KHUHIRUH WKLV UHVHDUFK ZLOO DLP DW VROYLQJ (T f IRU URERWV ZLWK IRXU ILYH DQG VL[ MRLQW D[HV $OWKRXJK WKH WHFKQLTXHV GHVFULEHG LQ WKLV WH[W FDQ EH DSSOLHG WR PDQLSXODWRUV KDYLQJ SULVPDWLF MRLQWV 0DQVHXU DQG 'RW\ f ZH FRQFHQWUDWH RQ DOOUHYROXWH VL['2) PDQLSXODWRUV Q LV VL[ DQG DOO MRLQWV DUH DVVXPHG UHYROXWH PAGE 21 &+$37(5 (;,67,1* 62/87,216 &ORVHG)RUP $UFKLWHFWXUHV 7KH DELOLW\ WR FRPSXWH WKH FRRUGLQDWHV LQ MRLQW VSDFH RI DQ HQGHIIHFWRU SRVH JLYHQ LQ &DUWHVLDQ VSDFH LV DQ LPSRUWDQW FULWHULRQ LQ WKH GHVLJQ RI FRPSXWHUFRQWUROOHG PDQLSXODWRUV $ GHVLUDEOH SURSHUW\ IRU DQ LQGXVWULDO PDQLSXODWRU LV WKH SRVVLELOLW\ RI FRPSXWLQJ WKH MRLQW YDULDEOHV QHFHVVDU\ WR SRVLWLRQ DQG RULHQW WKH HQGHIIHFWRU DV VSHFLILHG LQ &DUWHVLDQ VSDFH LQ FORVHGIRUP 3LHSHU f KDV VKRZQ WKDW D FORVHGIRUP VROXWLRQ LV SRVVLEOH ZKHQ WKH PDQLSXODWRU KDV WKUHH DGMDFHQW MRLQW D[HV LQWHUVHFWLQJ DW D FRPPRQ SRLQW 7KH LQYHUVH NLQHPDWLF SUREOHP UHGXFHV WKHQ WR D TXDUWLF SRO\QRPLDO HTXDWLRQ LQ RQH RI WKH MRLQW YDULDEOHV 0DQLSXODWRUV ZLWK WKH ODVW WKUHH MRLQW D[HV LQWHUVHFWLQJ DUH VDLG WR EH ZULVWSDUWLWLRQHG &RPSXWDWLRQDOO\ HIILFLHQW PHWKRGV IRU FRPSXWLQJ WKH SRVLWLRQ YHORFLW\ DQG DFFHOHUDWLRQ LQYHUVH NLQHPDWLFV IRU WKLV W\SH RI PDQLSXODWRUV KDYH EHHQ SUHVHQWHG E\ )HDWKHUVWRQH f +ROOHUEDFK DQG 6DKDU f 3DXO DQG =KDQJ f DQG /RZ DQG 'XEH\ f 6HYHUDO LQGXVWULDO VL[ DQG ILYH'2) PDQLSXODWRUV VXFK DV WKH 380$ VHULHV URERWV DUH RI WKH ZULVWSDUWLWLRQHG W\SH ,I RQ WRS RI PAGE 22 KDYLQJ D ZULVW WKH PDQLSXODWRU KDV VRPH DGGHG VWUXFWXUDO IHDWXUH VXFK DV WZR SDUDOOHO RU LQWHUVHFWLQJ MRLQW D[HV WKHQ FORVHGIRUP VROXWLRQV PD\ EH REWDLQHG LQ D VLPSOHU IRUP WKDQ D TXDUWLF SRO\QRPLDO HTXDWLRQ 7KLV LV WKH FDVH RI WKH 380$ URERW ZKRVH LQYHUVH NLQHPDWLFV DUH GLVFXVVHG LQ ([DPSOH RI &KDSWHU $Q DOJHEUDLF PHWKRG IRU VROYLQJ WKH LQYHUVH NLQHPDWLFV RI WKH 380$ FDQ EH IRXQG LQ &UDLJ f DQG D JHRPHWULF DSSURDFK LV GHVFULEHG LQ )X *RQ]DOH] t /HH f $QRWKHU VXIILFLHQW FRQGLWLRQ IRU FORVHGIRUP VROXWLRQV LV WKDW WKUHH DGMDFHQW MRLQW D[HV EH SDUDOOHO 'XII\ )X *RQ]DOH] t /HH f 5HFRUG DQG 3OD\EDFN $Q LQGXVWULDO URERW PDQLSXODWRU LV XVXDOO\ HTXLSSHG ZLWK VHQVRUV WKDW FDQ PHDVXUH LQIRUPDWLRQ VXFK DV MRLQW YDULDEOH YDOXHV DQG UDWHV RI FKDQJH RI WKRVH YDOXHV $ PHWKRG WKDW DYRLGV WKH FRPSXWDWLRQDO FRPSOH[LW\ RI WKH LQYHUVH NLQHPDWLF SUREOHP DOWRJHWKHU FRQVLVWV RI UHPRWHO\ JXLGLQJ D URERW HQGHIIHFWRU WUDMHFWRU\ E\ DFWLYDWLQJ HDFK MRLQW VHSDUDWHO\ ZKLOH VWRULQJ MRLQW VSDFH FRRUGLQDWHV DQG LQIRUPDWLRQ IURP WKH VHQVRUV DW VHOHFWHGnSRLQWV DORQJn WKHn WUDMHFWRU\ 7KH URERW FDQ WKHQ LQGHILQLWHO\ UHSHDW WKH UHFRUGHG PRWLRQ 6KRXOG WKH URERW EH QHHGHG IRU D GLIIHUHQW WDVN RU VKRXOG D FKDQJH LQ WKH ZRUNFHOO RFFXU WKDW UHTXLUHV GLIIHUHQW HQGHIIHFWRU WUDMHFWRULHVnnWKHfPRWLRQ RI WKHURERW ZLOO KDYH WR EH UHFRUGHG DJDLQ PAGE 23 1XPHULFDO 7HFKQLTXHV 0DQ\ VL[ DQG ILYH'2) NLQHPDWLF VWUXFWXUHV ODFN WKH QHFHVVDU\ DUFKLWHFWXUDO VLPSOLFLW\ IRU FORVHGIRUP LQYHUVH NLQHPDWLF VROXWLRQV 6ROYLQJ VXFK PDQLSXODWRUV UHTXLUHV WKH XVH RI QXPHULFDO LWHUDWLYH WHFKQLTXHV )RU VL['2) URERWV HTXDWLRQ f FDQ EH H[SUHVVHG DV D V\VWHP RI VL[ QRQOLQHDU HTXDWLRQV LQ WKH VL[ MRLQW YDULDEOHV RI WKH IRUP A k # H n f 3 I n k k n n f 3 I p@B k k p n n f 3 Ipn k k H n f D I L k k p n n f k I p &' WR k p n n f ZKHUH S[ 3\ DQG S] DUH WKH FRRUGLQDWHV RI WKH RULJLQ RI WKH HQGHIIHFWRU IUDPH DQG D DQG S DUH HLWKHU WKH (XOHU DQJOHV RU WKH UROOSLWFK\DZ DQJOHV GHULYHGn IURP WKH RULHQWDWLRQ PDWUL[ 5 RI WKH HQGHIIHFWRU IUDPH 3DXO f 7KH VL[GLPHQVLRQDO HTXDWLRQ LV WKHQ VROYHG E\ XVH RI D GLUHFW RU PRGLILHG 1HZWRQ5DSKVRQ RU VLPLODU WHFKQLTXH 0XOWLGLPHQVLRQDO LWHUDWLYH WHFKQLTXHV IRU VROYLQJ WKH LQYHUVH NLQHPDWLFV SUREOHP RI PDQLSXODWRUV RI DUELWUDU\ DUFKLWHFWXUH DUH GHVFULEHG E\ $QJHOHV f *ROGHKEHIJ\ %HKKDELE )HQWRUU fnA *•OGQEIJADKG /DZUHQFH f 7KH FRPSXWDWLRQDO HIILFLHQF\ RI WKHVH PAGE 24 PHWKRGV LV KLQGHUHG E\ WKH QHHG WR FRPSXWH WKH LQYHUVH RI WKH PDQLSXODWRU -DFRELDQ DW VHYHUDO SRLQWV /LQDUHV t 3DJH f DQG .D]HURXQLDQ f GHVFULEH WHFKQLTXHV WKDW VROYH WKH LQYHUVH NLQHPDWLF SUREOHP E\ YDU\LQJ RQH MRLQW YDULDEOH DW D WLPH VR DV WR PLQLPL]H WKH GLIIHUHQFH PHDVXUHG E\ D GHILQHG QRUP EHWZHHQ WKH HQG HIIHFWRU SRVH DV FRPSXWHG IURP WKH FXUUHQW MRLQW YDULDEOHV YDOXHV DQG WKH GHVLUHG SRVH 7KLV WHFKQLTXH KDV WKH DGYDQWDJHV RI JXDUDQWHHG FRQYHUJHQFH DQG UHOLDELOLW\ HYHQ DW D VLQJXODU SRVLWLRQ 7KLV PHWKRG UHTXLUHV FRPSXWDWLRQ RI WKH IRUZDUG NLQHPDWLFV DW HDFK LWHUDWLRQ DQG LW KDV D FRPSXWDWLRQDO FRPSOH[LW\ FRPSDUDEOH WR WKDW RI D 0RGLILHG PXOWLGLPHQVLRQDO 1HZWRQ5DSKVRQ $IWHU UHGXFLQJ WKH SUREOHP WR D SRO\QRPLDO V\VWHP RI IRXU HTXDWLRQV LQ RQO\ IRXU RI WKH MRLQW YDULDEOHV 7VDL DQG 0RUJDQ f XVHG D KRPRWRS\ PDS PHWKRG IRU VROYLQJ V\VWHPV RI SRO\QRPLDO HTXDWLRQV LQ VHYHUDO YDULDEOHV WR ILQG WKH VROXWLRQV RI WKH LQYHUVH NLQHPDWLFV SUREOHP RI UHYROXWH ILYH DQG VL[ GHJUHHRIIUHHGRP PDQLSXODWRUV RI DUELWUDU\ DUFKLWHFWXUH 7KH PHWKRG ILQGV DOO VROXWLRQV EXW LWV FRPSXWDWLRQDO FRPSOH[LW\ UHQGHUV LW LPSUDFWLFDO IRU PDQ\ DSSOLFDWLRQV /XPHOVN\ f SUHVHQWHG DQ LWHUDWLYH DOJRULWKP WKDW ILQGV HVWLPDWHV IRU WKUHH RI WKH MRLQW YDULDEOV DQG VROYHV LQ FORVHG IRUP IRU WKH UHPDLQLQJ WKUHH YDULDEOHV DW HDFK LWHUDWLRQ 7KH PHWKRG DSSOLHV WR D SDUWLFXODU W\SH RI DUP PAGE 25 JHRPHWU\ WKDW RI WKH *3 URERW GLVFXVVHG LQ ([DPSOH &KDSWHU RI WKLV GLVVHUWDWLRQf DQG FRQYHUJHV WR DQ DFFXUDWH HQGHIIHFWRU SRVLWLRQ EXW WR D OHVV DFFXUDWH DSSUR[LPDWLRQ RI WKH HQGHIIHFWRU RULHQWDWLRQ PAGE 26 &+$37(5 1(: $3352$&+ /LQN)UDPHV $VVLJQPHQW 6RPH VLPSOLILFDWLRQ LQ WKH PDWKHPDWLFDO GHVFULSWLRQ RI WKH LQYHUVH NLQHPDWLFV SUREOHP FDQ EH REWDLQHG LI FHUWDLQ VLPSOH UXOHV IRU DVVLJQLQJ WKH OLQNIUDPHV DUH DSSOLHG ,Q VHOHFWLQJ IUDPH )A WKH GLUHFWLRQ RI YHFWRU LV DOZD\V FKRVHQ VR WKDW WZLVW DQJOH LV LQ WKH LQWHUYDO >7f ,I WKHQ YHFWRUV DQG ] DUH SDUDOOHO DQG WKH FRPPRQ QRUPDO FDQ EH DUELWUDULO\ ORFDWHG DORQJ ERWK D[HV ,Q WKLV FDVH WKH SRVLWLRQ RI )UDPH )MB VKRXOG EH FKRVHQ VR WKDW GA LV HTXDO WR ]HUR )RU DQ Q'2) URERW IUDPH )Q DWWDFKHG WR WKH HQG HIIHFWRU FDQ EH FKRVHQ VR WKDW LW GLIIHUV IURP OLQN IUDPH )Q RQO\ E\ D URWDWLRQ RI DQJOH Q DERXW ]QBL ,Q RWKHU ZRUGV )Q FDQ EH VHOHFWHG VR WKDW GQ DQ DQ ZLWKRXW ORVV RI JHQHUDOLW\ :H SURYH WKLV SRLQW IRU Q EXW LW LV YDOLG IRU DQ\ UHOHYDQW YDOXH RI Q /HW XV DVVXPH WKDW (T f LV WR EH VROYHG ZLWK D '2) PDQLSXODWRU IRU ZKLFK G DJ RU DJ LV QRW HTXDO WR WKHQ WKH KRPRJHQHRXV PDWUL[ WUDQVIRUP $J GHFRPSRVHV LQWR PAGE 27 DV JLYHQ LQ (T f (TXDWLRQ f LV WKHQ HTXLYDOHQW WR $ $ $ $ $ S % ZKHUH WKH ULJKW KDQG VLGH RI WKLV ODVW HTXDWLRQ LV VHHQ WR EH D FRQVWDQW SRVH PDWUL[ IRU D PDQLSXODWRU GHVFULEHG E\ WKH OHIW KDQG VLGH LH RQH IRU ZKLFK G D D VR WKDW $af§ Af :KHQ MRLQW LV QRW SULVPDWLF GA LV FRQVWDQW DQG WKH RULJLQ RI WKH EDVH IUDPH )4 FDQ EH SRVLWLRQHG VR WKDW GA LV HTXDO WR 7KH 5HGXFHG 6\VWHP RI (TXDWLRQV )RU D '2) DUP (T f EHFRPHV $ $ $ $ $ $ S f DQG LW \LHOGV WZHOYH QRQ WULYLDO VFDODU HTXDWLRQV LQ WKH VL[ XQNQRZQ YDULDEOHV ,W LV GHVLUDEOH WR UHGXFH WKLV V\VWHP WR D PLQLPDO QXPEHU RI HTXDWLRQV LQYROYLQJ DV IHZ RI WKH MRLQW YDULDEOHV DV SRVVLEOH )RU DOOUHYROXWH '2) PDQLSXODWRUV 7VDL DQG 0RUJDQ f KDYH HVWDEOLVKHFI WKDW ZLWK UHVSHFW WR IUDPH ) WKH ]FRPSRQHQW RI WKH SRVLWLRQ YHFWRU S DQG WKDW RI YHFWRU W DORQJ ZLWK WKH LQQHU SURGXFWV WSM DQG SSf SURYLGH HTXDWLRQV LQ RQO\ RI WKH XQNQRZQV WKHUHE\ UHGXFLQJ WKH FRPSOH[LW\ RI WKH SUREOHP 7KH SURFHVV RI REWDLQLQJ WKHVH IRXU HTXDWLRQV PAGE 28 LQYROYHG PXOWLSO\LQJ WKH $PDWULFHV DQG VLPSOLI\LQJ WKH H[SUHVVLRQV REWDLQHG IRU WKH HOHPHQWV RI W DQG S %HVLGHV EHLQJ OHQJWK\ WKLV PHWKRG GRHV QRW DOORZ LQVLJKW LQWR WKH PHFKDQLVPV WKDW PDNH WKH VLPSOLILFDWLRQV SRVVLEOH 7KH DSSURDFK SUHVHQWHG KHUH SURYLGHV WKH VDPH UHVXOWV ZLWK PXFK OHVV HIIRUW DQG JUHDWHU LQVLJKW E\ WDNLQJ DGYDQWDJH RI WKH SURSHUWLHV RI URWDWLRQ WUDQVIRUPDWLRQV %\ ZULWLQJ WKH SURGXFW RI WZR $ PDWULFHVnLQ WKH IRUP 5M5M 5LOM OLf ZH GLYLGH (T f LQWR D SRVLWLRQ HTXDWLRQ S 55555ffff f DQG DQ RULHQWDWLRQ HTXDWLRQ 5 5MA 5 5 5 5J 5J f f :LWK WKH IUDPH DVVLJQPHQW FRQYHQWLRQV GLVFXVVHG ZKHQ MRLQW LV UHYROXWH (TXDWLRQ f WKHQ VLPSOLILHV WR S 5555fffL f 7KUHH LQGHSHQGHQW VFDODU HTXDWLRQV IRU S[ 3\ DQG S] FDQ EH REWDLQHG IURP (T f DQG PRUH HTXDWLRQV FDQ EH VHOHFWHG RXW RI WKH VFDODU HTXDWLRQV LPSOLHG E\ (T f PAGE 29 6LQFH URWDWLRQV DUH RUWKRJRQDO WUDQVIRUPDWLRQV WKH\ OHDYH LQQHU SURGXFWV LQYDULDQW KHQFH 5 X 5 Y X Y f IRU DQ\ URWDWLRQ PDWUL[ 5 DQG DQ\ YHFWRUV X DQG Y $ VSHFLDO FDVH RI f WKDW LV YHU\ XVHIXO LV 5 X Y X 5BY f 7KHVH SURSHUWLHV DUH H[WUHPHO\ HIILFLHQW LQ HOLPLQDWLQJ DOJHEUDLF WHUPV DQG XQQHFHVVDU\ MRLQW YDULDEOHV ZKHQ DSSOLHG WR (TV f DQG f LI LW LV IXUWKHU UHFRJQL]HG WKDW rL AL > A LU @ DQG f 5L] >DLUL@ f ZKHUH ] > @7 DUH DOZD\V LQGHSHQGHQW GXH WR WKH IUDPH DVVLJQPHQWV GLVFXVVHG DERYH 5 ] 5B ] ] RI A $OVR LQ DOO FDVHV VLQFH IUDPH )J LV FKRVHQ WR IRUFH D rr %\ UHSHDWHG XVH RI (TV f DQG f UHGXFHG HTXDWLRQV IURP (TV f DQG f ZH REWDLQ IRXU W] HDXDWLRQ W W ] 5 ]f ] W 5L 5 5 5 5 ]f ] W] 5O U U U 5 ]f f ] W] ] 5 5B 5 5B 5M ]f f PAGE 30 S] HTXDWLRQ S 5A 5 5 5A ZLWK T 5BO 5 5B 5OOOLfff VR WKDW S S ] T 5B 5 5 5Af ] f SW HTXDWLRQ S W 5T f ] f SS HTXDWLRQ SS S TT T f 6LQFH 5A A DQG 5 -] DUH LQGHSHQGHQW RI A (TV f DQG ff YHFWRU T DQG (TV ff DUH HDVLO\ VHHQ WR EH LQGHSHQGHQW RI WKH ILUVW DQG ODVW MRLQW YDULDEOHV DQG WKHUHIRUH IRUP D V\VWHP RI HTXDWLRQV LQ XQNQRZQV )LJXUH LOOXVWUDWHV WKLV GLVFXVVLRQ :LWK YHFWRU W ZKLFK FRLQFLGHV ZLWK ] DQG WKH SRVLWLRQ YHFWRU S RI WKH RULJLQ RI IUDPH ) DUH LQYDULDQW LQ WKH URWDWLRQ 5t URWDWLRQ DERXW ] ZKLFK FDQ RQO\ DIIHFW WKH HQGHIIHFWRU RULHQWDWLRQf 5RWDWLRQ DERXW ]4 KDV QR HIIHFW RQ WKH ] FRPSRQHQW RI DQ\ YHFWRU H[SUHVVHG LQ IUDPH )T +HQFH S] DQG W] DUH LQGHSHQGHQW RI DV ZHOO )LQDOO\ VLQFH URWDWLRQ DERXW =T PRYHV DOO WKH URERWLF VWUXFWXUH DV D EORF LW GRHV QRW DIIHFW WKH OHQJWK RI YHFWRU S RU WKH LQQHU SURGXFW RI W DQG S ‘ PAGE 31 n H )LJXUH 5RWDWLRQV DERXW ]4 RU ] GR QRW DIIHFW W] S] WS DQG SS PAGE 32 7KH UHGXFHG V\VWHP RI HTXDWLRQV ff GHWHUPLQHV FDQGLGDWH VROXWLRQV IRU MRLQW YDULDEOHV DQG 2QFH WKLV V\VWHP RI HTXDWLRQV LV VROYHG WKH UHPDLQLQJ WZR YDULDEOHV FDQ EH IRXQG E\ XVLQJ PRUH HTXDWLRQV IURP f DQG WKHQ WHVWHG IRU FRQVLVWHQF\ 7KH SRZHU RI WKLV DSSURDFK ZLOO EHFRPH DSSDUHQW IRU VSHFLILF PDQLSXODWRUV DV IXUWKHU VLPSOLILFDWLRQ XVLQJ (TV ff EHFRPHV REYLRXV )XUWKHUPRUH VLPSOLILFDWLRQ E\ XVH RI URWDWLRQ LQQHUSURGXFW LQYDULDQFH LV FRPSXWDWLRQDOO\ HFRQRPLFDO DQG SURYLGHV JUHDWHU LQVLJKW LQWR WKH VWUXFWXUH DQG SURSHUWLHV RI WKH LQYHUVH NLQHPDWLF HTXDWLRQV $GGLWLRQDO ,QYHUVH .LQHPDWLFV (TXDWLRQV (TXDWLRQV ff DUH QHFHVVDU\ EXW QRW VXIILFLHQW $OWKRXJK WKH\ DUH VDWLVILHG E\ DOO VROXWLRQ VHWV RI (T f WKH\ DUH DOVR LQ JHQHUDO VDWLVILHG E\ H[WUDQHRXV VROXWLRQV 7KLV SUREOHP ZDV UHSRUWHG E\ 7VDL DQG 0RUJDQ f DV ZHOO $QRWKHU SUREOHP ZLWK FRQVLGHULQJ (TV ff DORQH LV WKH SUHVHQFH RI VLJQ DPELJXLWLHV ,Q PDQ\ SUDFWLFDO VLWXDWLRQV RQH RI WKH HTXDWLRQV ZLOO DOORZ D FORVHGIRUP VROXWLRQ IRU HLWKHU WKH VLQH RU WKH FRVLQH IXQFWLRQ RI D UHYROXWH YDULDEOH 7KH RWKHU IXQFWLRQ QHHGV WR EH FRPSXWHG XVLQJ WKH 3\WKDJRUHDQ LGHQWLW\ ZKLFK RIIHUV WZR YDOXHV RSSRVLWH LQ VLJQ $OWKRXJK ERWK VLJQV FDQ EH WULHG LQ WKH VHDUFK IRU D VROXWLRQ LQ VRPH FDVHV WKH QXPEHU PAGE 33 RI VLJQ DPELJXLWLHV FDQ EH UHGXFHG E\ FRQVLGHULQJ PRUH FRQVWUDLQWV IURP (TV f DQG f $GGLWLRQDO HTXDWLRQV ZLOO DOVR KHOS ILOWHU RXW H[WUDQHRXV VROXWLRQV DQG LQ VRPH FDVHV ZLOO HDVH WKH VROXWLRQILQGLQJ SURFHVV UDWKHU WKDQ FRPSOLFDWH LW 7KH [ DQG \FRPSRQHQWV RI YHFWRUV W DQG S SURYLGH FRQYHQLHQW DGGLWLRQDO FRQVWUDLQWV DW WKH FRVW RI LQWURGXFLQJ WKH YDULDEOH (TXDWLRQV W[ 5M 5 5 5M ] [ f W\ 5 5 5 5 ] \ f 3[ A A A AArfA f f rA A Af r ;n f DQG 3\ A A A AAAf A f A A AA r < f ZKHUH ; DQG \ DUH WKH XVXDO FDQRQLFDO XQLW YHFWRUV DUH VWLOO LQGHSHQGHQW RI 6ROYLQJ ,QYHUVH .LQHPDWLF (TXDWLRQV 2QFH WKH UHGXFHG VHW RI HTXDWLRQV ff DQG WKH DGGLWLRQDO HTXDWLRQV ff KDYH EHHQ H[SDQGHG WKH SUREOHP EHFRPHV WKDW RI H[WUDFWLQJ WKH YDOXHV RI WKH MRLQW DQJOHV IURP WKH HTXDWLRQV ZKLFK DUH LQ WHUPV RI WKH VLQHV PAGE 34 DQG FRVLQHV RI WKH DQJOHV ,Q WKLV VHFWLRQ ZH GHVFULEH VRPH RI WKH WHFKQLTXHV WKDW FDQ EH XVHG IRU WKLV WDVN &HUWDLQ VLPSOH DUP JHRPHWULHV DOORZ D FORVHG IRUP VROXWLRQ )RU VXFK DUPV RQH RI WKH HTXDWLRQV ZLOO KDYH WKH IRUP D 6 E & G ZKHUH 6 DQG & DUH WKH VLQH DQG FRVLQH UHVSHFWLYHO\ RI VRPH DQJOH ,I WKH FRQVWDQWV D E DQG G DUH NQRZQ WKHQ WKHUH DUH WZR SRVVLEOH VROXWLRQV ZKHQ D E G DWDQ>GsDEGf@ DWDQEDf ZKHUH DWDQYZf UHWXUQV WKH DQJOH DUFWDQYZf DGMXVWHG WR WKH SURSHU TXDGUDQW DFFRUGLQJ WR WKH VLJQ RI WKH UHDO QXPEHUV Y DQG Z $ VSHFLDO FDVH RFFXUV ZKHQ D RU E 7KH HTXDWLRQ FDQ WKHQ EH VROYHG IRU 6 RU & VHSDUDWHO\ 7KH RWKHU YDULDEOH FDQ EH REWDLQHG IURP WKH 3\WKDJRUHDQ LGHQWLW\ ‘‘ 6 F f ZLWK D VLJQ DPELJXLW\ $JDLQ WKLV OHDGV WR WZR SRVVLEOH YDOXHV IRU WKH DQJOH DWDQ6 s 6ff LI 6 LV FRPSXWHG RU DWDQs &f &f LI & LV WKH NQRZQ YDULDEOH $ YDOXH RI k FDQ EH GLUHFWO\ DQG XQLTXHO\ REWDLQHG ZKHQ WZR OLQHDU HTXDWLRQV LQ WKH VLQH DQG FRVLQHV RI RQH DQJOH PAGE 35 DUH REWDLQHG ,Q WKLV FDVH WKH YDOXHV RI 6 DQG & DUH FRPSXWHG DQG WKH DQJOH LV WKHQ JLYHQ E\ DWDQ6 &f ([FKDQJLQJ %DVH DQG (QG(IIHFWRU )UDPHV 7KH LQYHUVH NLQHPDWLFV SUREOHP FRQVLVWV RI ILQGLQJ MRLQW YDULDEOHV WKDW UHDOL]H D JLYHQ UHODWLRQVKLS EHWZHHQ WZR IUDPHV WKH EDVH IUDPH )4 DQG WKH HQGHIIHFWRU IUDPH )Q 7KH UROHV RI WKHVH WZR IUDPHV DUH LQ IDFW LQWHUFKDQJHDEOH DV ZH LOOXVWUDWH LQ )LJXUH 7KLV PHDQV WKDW WKH SUREOHP FDQ EH YLHZHG DV ILQGLQJ WKH MRLQW YDULDEOHV QHFHVVDU\ IRU WKH URERW WR DFKLHYH WKH EDVH IUDPH DV YLHZHG IURP WKH HQG HIIHFWRU IUDPH 7KLV SUREOHP UHYHUVDO UHTXLUHV WKDW WKH '+ SDUDPHWHUV EH UHDUUDQJHG DQG LQWHUPHGLDWH IUDPHV EH UHDVVLJQHG DV LOOXVWUDWHG LQ )LJXUH EXW LW FDQ EH XVHIXO LQ PDQ\ ZD\V )RU H[DPSOH VHYHUDO FRPSXWDWLRQDOO\ HIILFLHQW LQYHUVH NLQHPDWLF WHFKQLTXHV KDYH EHHQ GHYHORSHG IRU URERWV ZLWK WKH ODVW WKUHH MRLQW D[HV LQWHUVHFWLQJ DW D FRPPRQ SRLQW )HDWKHUVWRQH +ROOHUEDFK DQG VDKDU 3DXO DQG =KDQJ /RZ DQG 'XEH\ f 7KH VDPH WHFKQLTXHV FDQ EH XVHG IRU D URERW ZKRVH ILUVW WKUHH D[HV LQWHUVHFW E\ UHYHUVLQJ WKH UROHV RI HQF/HIIHFWRU DQG EDVH IUDPH ,Q WKH QH[W FKDSWHUV ZH ZLOO XVH WKLV SUREOHP UHYHUVDO WHFKQLTXH WR DYRLG UHSHWLWLRXV GHYHORSPHQWV PAGE 36 HQGHIIHFWRU )LJXUH ,QWHUFKDQJLQJ EDVH DQG HQGHIIHFWRU IUDPHV PAGE 37 &+$37(5 62/9,1* '2) 0$1,38/$7256 5HGXFHG 6\VWHP RI (TXDWLRQV )RU '2) URERW DUPV WKH LQYHUVH NLQHPDWLF SUREOHP LV VROYHG ZKHQ MRLQW YDOXHV DUH IRXQG WKDW VDWLVI\ WKH HTXDWLRQ $O $ $ $ 3 f (TXDWLRQ f GHFRXSOHV LQWR D SRVLWLRQ HTXDWLRQ 5[ 5 5 f f S f DQG DQ RULHQWDWLRQ HTXDWLRQ JLYHQ E\ 5[ 5 5 5 5 f :KHQ WKH IRXUWK MRLQW LV UH\ROXWH LV REWDLQHG E\ SURSHU FKRLFH RI IUDPH ) DQG (T f VLPSOLILHV WR 5S 5 f A S f $ UHGXFHG V\VWHP RI IRXU HTXDWLRQV LQ WKH VLQHV DQG FRVLQHV RI MRLQW DQJOHV A DQG FDQ EH GHULYHG E\ FRQVLGHULQJ WKH TXDQWLWLHV W] S] DQG WKH LQQHU SURGXFWV WS DQG SS H[SUHVVHG LQIUDPH )A PAGE 38 9HFWRU W LV JLYHQ E\ W 5 ] 5O 5 5 5 ] ZKHUH ] LV WKH WKLUG FDQRQLFDO XQLW YHFWRU ] > @7 6LQFH WZLVW DQJOH Dc LV HTXDO WR 5 ] >D 6 D & W@rA > O@A ] DQG WKH H[SUHVVLRQ IRU W VLPSOLILHV WR W 5[ 5 5 = f 0XOWLSO\LQJ E\ 5A \LHOGV 5A W 5 5 ] DQG WKH LQQHU SURGXFW RI HDFK VLGH RI WKLV HTXDOLW\ ZLWK YHFWRU ] SURYLGHV ] f 5@B A Wf ] 5 5 f (T f DSSOLHG WR ERWK VLGHV RI WKLV ODVW HTXDWLRQ JLYHV 5 ] W 5 ] 5 ] RU 5 ]fW 5B ]f5 ]f f 6LQFH 5B ] > FU W@7 GRHV QRW GHSHQG RQ k WKLV ODVW HTXDWLRQ LV LQGHSHQGHQW RI MRLQW YDULDEOHV DQG 6XEWUDFWLQJ YHFWRU IURP ERWK VLGHV RI (T f DQG PXOWLSO\LQJ E\ 5a \LHOGV PAGE 39 5 ; 5O 3 Of f DQG WDNLQJ WKH LQQHUSURGXFW ZLWK YHFWRU ] SURYLGHV ] 5 f ] f ] 5O Sf ] 5 A $SSO\LQJ f WR WKH ILUVW WHUP RI ERWK VLGHV RI WKLV HTXDWLRQ JLYHV DIWHU UHDUUDQJLQJ WHUPVf 5[ = S 5A = = 5 O = f 7KH ULJKW KDQG VLGH RI (T f LV FRQVWDQW VLQFH 0XOWLSO\LQJ (T f E\ 5 JLYHV Af 5 A A 5 A 5 A 3 f AOf f DQG PXOWLSOLFDWLRQ RI (T f E\ 5 5Lf 5B 5L S OA@A 5M W@ 5HSHDWHG XVH RI SURSHUWLHV f DQG f DQG UHRUGHULQJ VLPSOLILHV WKLV ODVW HTXDWLRQ WR GL&7L GLUL DQG ]OA GM/ DUH LQGHSHQGHQW RI A PAGE 40 AW a >5 f 5 =@ WS >5J A f =@ f (TXDWLRQ f LV DOVR LQGHSHQGHQW RI k DQG k 8VLQJ (T f WKH LQQHUSURGXFW SS VDWLVILHV SS f§ >5A 5 ,f A@ f >A A A AA A@ f ([SDQGLQJ WKH OHIW KDQG VLGH XVLQJ LQQHUSURGXFW LQYDULDQFH RI URWDWLRQV ZKHUH QHHGHG DQG UHDUUDQJLQJ WHUPV \LHOG ArA ; A 3rAO f§ W3r3 ArA ArA ArAAAr f (TXDWLRQV f f f DQG f IRUP D OLQHDU V\VWHP LQ WKH YDULDEOHV 6A &6 DQG & 7KH IRXU HTXDWLRQV REWDLQHG DUH DAW\ DAW[ tr A AAA A DOW[ 6 f DOIF\ & DD & &7O3[ 6 DO3\ & DD 6 DO3\ 6[ DO3[ &s DDG 6 DD & fDX OD U U f f f f ZLWK UO WS J GJ G[W] 77G 8 U7 f UOW= n UA UAGMA Wf G" UG Uf SS DGDGDGf GO3] UGG f f f f 7KH OLQHDU V\VWHP RI HTXDWLRQV IRUPHG E\ (TV ff ZLOO EH UHIHUUHG WR nDV WKH UHGXFHG V\VWHP IRU D IRXU'2) PAGE 41 PDQLSXODWRU $OWKRXJK G FDQ EH DVVXPHG ]HUR ZLWKRXW ORVV RI JHQHUDOLW\ IRU D '2) PDQLSXODWRU WKLV V\VWHP RI HTXDWLRQV ZLOO EH XVHG IRU '2) VHFWLRQV RI ODUJHU PDQLSXODWRUV QH[W FKDSWHUVf IRU ZKLFK WKH SDUDPHWHU FRUUHVSRQGLQJ WR GA ZLOO LQ JHQHUDO QRW EH ]HUR +HQFH GA LV DVVXPHG QRW HTXDO WR ]HUR DW WKLV SRLQW $ XQLTXH VROXWLRQ WR WKH UHGXFHG V\VWHP LV JLYHQ E\ f ‘ 6 UL & f§ U + ; 6 U R ZKHUH + DOW\ DOW[ DO3[ DO3\ DO3\ DO3[ DD DDG FWFW DD DDG DD f f ZKHQ PDWUL[ + LV QRQVLQJXODU 8QLTXH YDOXHV RI A DQG k DUH WKXV REWDLQHG IURP WKH YDOXHV RI 6A &A 6 DQG & 7KH FDVH ZKHUH + LV QRW LQYHUWLEOH LV GLVFXVVHG LQ WKH QH[W VHFWLRQV EHFDXVH RI LWV LQWHUHVWLQJ LPSOLFDWLRQV :LWK AA DQG NQRZQ (T f SURYLGHV DnZD\ WR VROYH IRU kf ,QGHHG ZKHQ H[SDQGHG WKH ILUVW FRPSRQHQWV \LHOG AA 7DAA A DDA a AOA[ AO3\ DO f PAGE 42 DQG DD&nA A f DA7DAA ra 7O6O3[ UO&O3\ DL3]fGLf f :KHQ WKH GHWHUPLQDQW RI WKLV OLQHDU V\VWHP RI HTXDWLRQV LQ 6 DQG & LV QRW D XQLTXH YDOXH RI FDQ EH FRPSXWHG 2WKHUZLVH ZH FDQ REWDLQ XQLTXHO\ IURP DQRWKHU OLQHDU V\VWHP RI HTXDWLRQV LQ 6 DQG & 7AHr7A A AA A AOA[ AOA\ f DQG FW6 6 ^Wr&-OUDUf & f§7WAABA\ DW] f GHULYHG IURP (T f 1RWH WKDW FDQ DOVR EH FRPSXWHG XVLQJ D V\VWHP RI WZR HTXDWLRQV IRUPHG E\ (T f RU (T f DQG RQH RI (TV f DQG f 7KH $SSHQGL[ VKRZV WKDW WKH GHWHUPLQDQWV RI WKH WZR V\VWHPV RI HTXDWLRQV DERYH DUH VLPXOWDQHRXVO\ ]HUR RQO\ ZKHQ MRLQW D[LV DOLJQV ZLWK DQRWKHU MRLQW D[LV ZKLFK SXWV WKH DUP LQ D GHJHQHUDWH FRQILJXUDWLRQ 7R FRPSOHWH WKH '2) VROXWLRQ VHW ZH XVH (T f ZKLFK FDQ EH UHZULWWHQ DV 5 5Mf 5B 5I 5 7KH ILUVW FROXPQ YHFWRU RI 5 REWDLQHG E\ PXOWLSO\LQJ ERWK VLGHV E\ WKH ILUVW FDQRQLFDO XQLW YHFWRU [ >@7 PAGE 43 f & Q[ 5 ; 6 5 UB 5A 5 ; 5 5 5[ Q\ Q] FDQ EH XVHG WR FRPSXWH WKH ODVW YDULDEOH k 7KLV VKRZV WKDW D '2) LQYHUVH NLQHPDWLF SUREOHP ZLOO LQ JHQHUDO JHQHUDO LQ WKH VHQVH WKDW PDWUL[ + LV QRQVLQJXODUf \LHOG D XQLTXH VROXWLRQ VHW +RZHYHU IRU VRPH PDQLSXODWRU JHRPHWULHV DQGRU VRPH SDUWLFXODU HQGHIIHFWRU SRVHV WKH SUREOHP PD\ KDYH PRUH WKDQ RQH VROXWLRQ 6SHFLDO '2) 0DQLSXODWRU *HRPHWULHV (TXDWLRQ f LV YDOLG RQO\ ZKHQ PDWUL[ + LV LQYHUWLEOH 7KH GHWHUPLQDQW RI PDWUL[ + FRPSXWHG IURP (T f LV JLYHQ E\ G+ DO D DOWD D : D Z! r r D G Z@ R D >D D D Gf R DU@ Z f ZKHUH WKH TXDQWLWLHV Z Z Z DQG Z DUH GHILQHG LQ WHUPV RI WKH FRPSRQHQWV RI SRVH YHFWRUV W DQG S DV : W[ Z S[ S< Z 3[ IF[ Z 3[ IF\ f 3\ IF[r ‘ PAGE 44 $QDO\]LQJ (TXDWLRQ f VKRZV WKDW WKH YDOXH RI G+ GHSHQGV RQ WKH VHYHQ URERW SDUDPHWHUV DD D DA D D DQG G DV ZHOO DV WKH SRVH TXDQWLWLHV Z Z Z DQG Z +RZHYHU IRU FHUWDLQ URERW VWUXFWXUHV G+ LV HTXDO WR ]HUR QR PDWWHU ZKDW WKH HQGHIIHFWRU SRVH LV 7KH H[SUHVVLRQ RI G+ DERYH SURYLGHV XV ZLWK D ZD\ WR ILQG DOO VXFK '2) URERW JHRPHWULHV 'XH WR RXU OLQN IUDPHV DVVLJQPHQW WKH RQO\ URERW SDUDPHWHU LQ WKH H[SUHVVLRQ RI GA WKDW FDQ EH QHJDWLYH LV G %\ H[SDQGLQJ (T f ZH JHW GD D D A r r D A D D DAA D G Z DA D D D Z D[ D D D G Z D D DA D Z f ZKHUH RQO\ WKH TXDQWLWLHV G Z DQG Z FDQ EH QHJDWLYH ,I DQ DUP VWUXFWXUH LV VXFK WKDW G+ LV ]HUR IRU HYHU\ SRVVLEOH HQGHIIHFWRU SRVH WKHQ G+ ZLOO EH ]HUR HYHQ IRU D SRVH ZLWK SRVLWLYH Z DQG Z ,I ZH DVVXPH Z DQG Z QRQ QHJDWLYH WKHQ ZLWK G QHJDWLYH G+ FDQ EH ]HUR LI WKH HTXDOLW\ f§ FUA A DO D G Z f§ r r DO D D ZA D D D DO D : D/ FW D D Z r r D D G Z D D D[ D Z KROGV +RZHYHU VXFK DQ HTXDOLW\ LV DFWXDOO\ D FRQGLWLRQ RQ SRVH TXDQWLWLHV Z Z Z DQG Z :H FRQFOXGH WKDW URERW PAGE 45 VWUXFWXUHV IRU ZKLFK G+ LV DOZD\V ]HUR LQGHSHQGHQW RI WKH HQGHIIHFWRU SRVHf KDYH '+SDUDPHWHUV RA FU D D D D DQG G IRU ZKLFK HDFK RI WKH VL[ WHUPV LQ (T f LV LQGLYLGXDOO\ ]HUR 7KHVH WHUPV LQ WXUQ DUH ]HUR ZKHQ SDUWLFXODU VWUXFWXUH SDUDPHWHUV DUH HTXDO WR ]HUR )RU H[DPSOH "L FU ZLOO PDNH WKH GHWHUPLQDQW ]HUR ,Q RUGHU WR HQXPHUDWH WKH PLQLPXP QXPEHU RI GLVWLQFW FRPELQDWLRQV RI ]HUR SDUDPHWHUV WKDW PDNH G+ ZH H[DPLQH DOO SRVVLEOH FDVHV ZKHQ D SDUWLFXODU SDUDPHWHU LV ]HUR :H JHW VHYHQ VLPSOHU H[SUHVVLRQV R I G+ OLVWHG LQ 7DEOH E\ VHSDUDWHO\ DVVXPLQJ HDFK UHOHYDQW SDUDPHWHU WR EH HTXDO WR ]HUR 7DEOH SURYLGHV D VLPSOH PHDQ IRU ILQGLQJ DOO SRVH LQGHSHQGHQWf '2) URERW JHRPHWULHV IRU ZKLFK PDWUL[ + ZLOO EH VLQJXODU ,Q WKH QH[W VHFWLRQ ZH VKRZ WKDW WKH LQYHUVH NLQHPDWLFV SUREOHP IRU VXFK URERWV FDQ VWLOO EH VROYHG E\ XVH RI WKH UHGXFHG V\VWHP RI HTXDWLRQV ff 6SHFLDO '2) $UP 6WUXFWXUHV $ WULYLDO FRQGLWLRQ RFFXUV ZKHQ WZR FRQVHFXWLYH MRLQW D[HV FRLQFLGH VRPHZKHUH DORQJ WKH DUP 6XFK D GHJHQHUDWH FRQGLWLRQ LV GHWHFWHG E\ DA IRU VRPH MRLQW L ,Q WKLV FDVH WKH PDQLSXODWRU ORVHV RQH GHJUHH RI IUHHGRP DQG EHFRPHV D UHGXQGDQW '2) DUP ,I D VROXWLRQ VHW H[LVWV IRU VXFK DQ DUP WKHUH ZLOO EH DQ LQILQLWH QXPEHU RI VROXWLRQ VHWV $ FDUHIXO DQDO\VLV RI 7DEOH VKRZV WKDW WKHUH DUH RQO\ WHQ PLQLPDO QRQWULYLDO FRQGLWLRQV RQ WKH DUP PAGE 46 7DEOH 6SHFLDO H[SUHVVLRQV IRU G+ &RQGLWLRQ G+ R ,, U+ E U+ r r DO D Z 2 ,, &0 E &0 DO r D D Z D a r A D D AA R + ,, 2 DO r D D D Gf Z D D r D DO DO G Z DO &7 GfZA D 2f D FW DL D Z G 3 2 RL R D D D Z D ZA D D D Ds D Df Z JHRPHWU\ SRVHLQGHSHQGHQWf IRU G+ $OO WHQ FRQGLWLRQV DUH OLVWHG DQG GHVFULEHG LQ 7DEOH DQG LOOXVWUDWHG LQ )LJXUH 7KH ILUVW WKUHH FRQGLWLRQV LQ 7DEOH IROORZ IURP WKH ILUVW HQWU\ RI 7DEOH &RQGLWLRQV DQG DUH GHULYHG IURP WKH VHFRQG HQWU\ LQ 7DEOH DIWHU GURSSLQJ GXSOLFDWH FRQGLWLRQV DOUHDG\ HVWDEOLVKHG &RQWLQXLQJ LQ WKLV IDVKLRQ DOO RI 7DEOH FDQ EH FRPSOHWHG 2EVHUYH WKDW HQWU\ LQ 7DEOH GRHV QRW DGG DQ\ QHZ FRQGLWLRQV LQWR 7DEOH VLQFH DOO PLQLPDO VHWV RI ]HUR SDUDPHWHUV LPSOLHG E\ G+ LQ HQWU\ KDYH DOUHDG\ EHHQ DFFRXQWHG IRUn ,W PXVW EH QRWHG WKDW G+ FDQ VWLOO EH ]HUR IRU '2) DUP JHRPHWULHV QRW OLVWHG LQ WKH SUHFHGLQJ 7DEOH +RZHYHU IURP WKH GLVFXVVLRQ DERYH ZH VHH cWKDW VXFK D VLWXDWLRQ FDQ RQO\ KDSSHQ DW SDUWLFXODU HQGHIIHFWRU SRVHV ZKHUHDV G+ ZLOO PAGE 47 7DEOH 6SHFLDO VWUXFWXUHV RI '2) PDQLSXODWRUV &RQGLWLRQ 'HVFULSWLRQ DO D )LUVW MRLQW D[HV f DUH SDUDOOHO )LUVW D[HV f DUH SDUDOOHO DQG /DVW D[HV f DUH SDUDOOHO D 2 )LUVW D[HV f DUH SDUDOOHO DQG ODVW D[HV f LQWHUVHFW R /DVW WKUHH D[HV f DUH SDUDOOHO D 2 0LGGOH D[HV f DUH SDUDOOHO DQG ODVW D[HV f LQWHUVHFW D 2 )LUVW D[HV f LQWHUVHFW t ODVW D[HV f DUH SDUDOOHO D r 0LGGOH D[HV f LQWHUVHFW t ODVW D[HV f DUH SDUDOOHO D D )LUVW D[HV f LQWHUVHFW t ODVW D[HV f LQWHUVHFW DO D G )LUVW D[HV f LQWHUVHFW D D 0LGGOH D[HV f LQWHUVHFW DQG ODVW D[HV f LQWHUVHFW EH ]HUR IRU WKH JHRPHWULHV GHVFULEHG LQ 7DEOH DW DQ\ SRVH :H QRZ H[DPLQH LQ GHWDLO WKH LQYHUVH NLQHPDWLFV RI HDFK RI WKH VSHFLDO '2) URERW DUFKLWHFWXUHV GHVFULEHG LQ 7DEOH DQG LOOXVWUDWHG LQ )LJXUH PAGE 48 )LUVW WKUHH MRLQW D[HV DUH SDUDOOHO $[HV DQG DUH SDUDOOHO DQG DUH SDUDOOHO $[HV DQG DUH SDUDOOHO D[HV DQG LQWHUVHFW $[HV DQG DUH SDUDOOHO $[HV DQG DUH SDUDOOHO $[HV DQG LQWHUVHFW DQG LQWHUVHFW DQG DUH SDUDOOHO )LJXUH 6SHFLDO '2) VWUXFWXUHV PAGE 49 $[HV DQG LQWHUVHFW DQG DUH SDUDOOHO $[HV DQG LQWHUVHFW DQG LQWHUVHFW $[HV DQG LQWHUVHFW $[HV DQG LQWHUVHFW DQG LQWHUVHFW )LJXUH f§&RQWLQXHG PAGE 50 7KH UHGXFHG V\VWHP RI HTXDWLRQV ff FDQ VWLOO EH HIILFLHQWO\ XVHG WR ILQG DOO WKH VROXWLRQ VHWV RI (T f ZKHQ PDWUL[ + LV VLQJXODU &DVH D D )LUVW WKUHH MRLQW D[HV DUH SDUDOOHO (QWU\ LQ 7DEOH f7KH UHGXFHG V\VWHP RI HTXDWLRQV EHFRPHV DOW\ 6 DOIF[ FO D&7 6 DO3\ V DO3[ &[ DD & U U U U f f f f (TXDWLRQV f DQG f DUH FRQVWUDLQWV RQ SRVH SDUDPHWHUV W] DQG S] UHVSHFWLYHO\ 2QO\ HQGHIIHFWRU SRVHV WKDW VDWLVI\ 3] GL G G DQG W] U (TV f DQG ff DUH VROYDEOH ZLWK WKLV DUP JHRPHWU\ (TXDWLRQVn f DQG f VWLOO DOORZ D VROXWLRQ LQ WKH VW\OH RI 3LHSHU f E\ ILUVW HOLPLQDWLQJ 6 DQG & IURP WKH HTXDWLRQV 7KLV FDQ EH GRQH E\ VROYLQJ IRU 6 DQG & DQG VXEVWLWXWLQJ LQ WKH 3\WKDJRUHDQ LGHQWLW\ f WR JHW ^>U/ DMW\ 6 D[W[ &f@DD` ^>UO DO3\ 6O DO3[ &f@DD` f :LWK WKH WULJRQRPHWULF LGHQWLWLHV 6 W[O W[f DQG &s WfO W[f PAGE 51 ZKHUH WA WDQ Af (T f \LHOGV D TXDUWLF SRO\QRPLDO HTXDWLRQ LQ WA :LWK A FRPSXWHG D YDOXH RI LV REWDLQHG DQG FDQ EH FRPSXWHG XQLTXHO\ IURP (TV f DQG f 7KH UHPDLQLQJ DQJOHV k DQG kf FDQ EH FRPSXWHG DV LQGLFDWHG HDUOLHU :H SURSRVH D PHWKRG WKDW DOORZV EHWWHU LQVLJKW ZLWKRXW WKH FRPSOH[LW\ RI D TXDUWLF SRO\QRPLDO HTXDWLRQ )RU VLPSOLFLW\ WKH VLQH DQG FRVLQH RI D VXP RI DQJOHV ZLOO EH UHSUHVHQWHG DFFRUGLQJ WR &AMMAFRV AMf DQG 6AM VLQAMf $V GHVFULEHG LQ FKDSWHU D VHW RI LQYHUVH NLQHPDWLF HTXDWLRQV FDQ EH REWDLQHG E\ H[SUHVVLQJ WKH FRPSRQHQWV RI YHFWRUV W DQG S DQG WKH LQQHU SURGXFWV WS DQG SS LQ WHUPV RI WKH MRLQW YDULDEOHV A REWDLQHG DUH L O 7KH HTXDWLRQV IF[ r 6 f IF\ ar & f S[ D & D & D/ &A f 3\ D 6 D 6 D[ 6s f WS Ds F DD 6 UGGf G f SS DD & DD & DsD &f FW f ZKHUH FW DA DA DA GA GA GA GG GAGM GGf (TXDWLRQV f DQG f \LHOG 6 DQG & GLUHFWO\! VR D XQLTXH YDOXH RI pO REWDLQHG PAGE 52 :LWK k NQRZQ (TV f DQG f EHFRPH HOERZ HTXDWLRQVf S[ a D & D & DO & nf 3\ f D 6 D 6 DO 6 nf DQG FDQ EH VROYHG IRU & E\ & WAS; f D &A A3\ f D 6A D D[@ D[ Df ZKLFK LV REWDLQHG E\ DSSO\LQJ WKH FRVLQH ODZ WR WKH WULDQJOH KDYLQJ OLQNV DQG DV LWV VLGHV 7ZR YDOXHV RI k IROORZ IURP k DWDQs -^&f &f DQG D XQLTXH YDOXH RI kA FDQ WKHQ EH FRPSXWHG IURP (TV nf DQG nf ZKLFK \LHOG D OLQHDU V\VWHP LQ 6A DQG & ZKHQ 6 DQG & DUH H[SDQGHG XVLQJ VXP RI DQJOHV WULJRQRPHWULF LGHQWLWLHV -RLQW YDULDEOH k LV JLYHQ E\ H H f HO f H DQG WKH VROXWLRQ VHW LV FRPSOHWHG ZKHQ WKH ODVW DQJOH k LV FRPSXWHG DV VKRZQ HDUOLHU 7KLV GHYHORSPHQW SURYHV WKDW WKHUH FDQ EH DW PRVW VROXWLRQ VHWV IRU D '2) DUP ZLWK WKLV SDUWLFXODU JHRPHWU\ &DVH FU FU 7KH ILUVW WZR MRLQW D[HV DUH SDUDOOHO DQG WKH ODVW WZR MRLQW D[HV DUH SDUDOOHO 7KH UHGXFHG V\VWHP LV PAGE 53 DnOW\ 6 DOW[ & UO f U f DD 6 U f DO3\ 6O DO3[ F[ &DG 6 DD A Ur f (TXDWLRQ f LPSRVHV D FRQVWUDLQW RQ SRVH SDUDPHWHU Wf W] W77 r WKLV FRQVWUDLQW LV VDWLVILHG (T f FDQ EH VROYHG DQG \LHOGV WZR GLVWLQFW YDOXHV IRU A 7KHQ (TV f DQG f IRUP D OLQHDU V\VWHP LQ 6 DQG & ZKLFK FDQ EH VROYHG XQLTXHO\ IRU H :LWK AA DQG H FRPSXWHG DQG k FDQ EH XQLTXHO\ REWDLQHG DV VKRZQ HDUOLHU +HUH DJDLQ ZH ILQG DW PRVW WZR VROXWLRQ VHWV &DVH FUM D )LUVW WZR MRLQW D[HV DUH SDUDOOHO DQG ODVW WZR MRLQW D[HV LQWHUVHFW 7KH UHGXFHG V\VWHP EHFRPHV DMW\ 6O W DAW[ DA 6 f§ AA A AL f DD A U f U f DO3\ 6 DA & U f )URP (T f WKH SRVH FRQVWUDLQW U WUDQVODWHV WR 3] GL G UG r )RU D SRVH PDWUL[ WKDW VDWLVILHV WKLV FRQVWUDLQW WZR SRVVLEOH YDOXHV RI FDQ EH REWDLQHG IURP (T f )RU HDFK RI WKRVH k YDOXHV D XQLTXH YDOXH RI k LV FRPSXWHG IURP WKH OLQHDU V\VWHP LQ 6 DQG &A IRUPHG E\ (TV f PAGE 54 DQG f 7KH WZR VROXWLRQ VHWV DUH WKHQ FRPSOHWHG DV VKRZQ SUHYLRXVO\ &DVH &7 &7 r 7KH ODVW WKUHH MRLQW D[HV DUH SDUDOOHO 7KH UHGXFHG V\VWHP VLPSOLILHV WR DOW\ 6 DOW[ FL UL f &7OW[ 6 DOW\ FL U rf &7O3[ 6 DOS\ & U f DO3\ V[ DO3[ &D DD & U f 7ZR RXW RI WKH ILUVW WKUHH HTXDWLRQV (TV ff f FDQ EH XVHG WR VROYH XQLTXHO\ IRU A 7KH WKLUG XQXVHG HTXDWLRQf EHFRPHV D UHDOL]DELOLW\ FRQVWUDLQW RQ WKH SRVH :LWK A NQRZQ (T f \LHOGV D YDOXH IRU & ZKLFK LQ WXUQ JLYHV WZR SRVVLEOH YDOXHV IRU k 7ZR VROXWLRQ VHWV FDQ EH REWDLQHG DIWHU FRPSXWLQJ DQG k &DVH D D 7KH LQWHUPHGLDWH MRLQW D[HV DUH SDUDOOHO DQG WKH ODVW WZR D[HV LQWHUVHFW 7KH UHGXFHG V\WHP EHFRPHV DMAW\ 6O DLW[ DFU 6 f§ UA f DOW; 6 DOW\ & U f &7OS[ 6 &7OS\ & U f DOS\ 6 DOS[ & U f 7ZR RXW RI WKH ODVW WKUHH HTXDWLRQV f f FDQ EH VROYHG XQLTXHO\ IRU A 7KH WKLUG HTXDWLRQ EHFRPHV D UHDOL]DELOLW\ FRQVWUDLQW RQ SRVH HOHPHQW W] RU S] GHSHQGLQJ PAGE 55 RQ WKH FKRVHQ HTXDWLRQ :LWK MA NQRZQ WZR YDOXHV RI FDQ EH FRPSXWHG IURP WKH YDOXH RI 6 GHULYHG IURP (T f &DVH D D 7KH ODVW WZR MRLQW D[HV DUH SDUDOOHO DQG WKH ILUVW WZR D[HV LQWHUVHFW 7KH UHGXFHG V\VWHP LV UO f DOW[ 6 a DOW\ & U f DO3[ 6 f DO3\ & f DD 6 U f &7DA A DD A U f (TXDWLRQ f LV D UHDOL]DELOLW\ FRQVWUDLQW RQ SDUDPHWHU W] (T ff )RU DQ HQGHIIHFWRU SRVH WKDW VDWLVILHV WKLV FRQVWUDLQW (T f \LHOGV WZR YDOXHV IRU A (TXDWLRQV f DQG f FDQ WKHQ EH VROYHG IRU k XQLTXHO\ &DVH &7 D r 7KH ODVW WZR MRLQW D[HV DUH SDUDOOHO DQG WKH LQWHUPHGLDWH WZR D[HV LQWHUVHFW 7KH UHGXFHG V\VWHP LV DOA\ s A UO f &7OW[ 6 f &7OW\ & U f DO3[ 6 f &7O3\ & DD 6 U rf DO3\ A DAS[ &[ 2DG 6 U f +HUH (TV f DQG f \LHOG D XQLTXH YDOX IRU WKHQ 2QH RI (TV f RU f FDQ EH XVHG WR VROYH IRU PAGE 56 6 WKHUHE\ SURYLGLQJ WZR YDOXHV IRU k WKH UHPDLQLQJ HTXDWLRQ LV D SRVH FRQVWUDLQW &DVH D D G 7KH ILUVW WKUHH MRLQW D[HV LQWHUVHFW DQG WKH UHGXFHG V\VWHP EHFRPHV ,, r‘ + f DOW[ 6 f IILW\ &/ UD & a U f &7O3; 6 f &7O3\ & f DD 6 U f U f (TXDWLRQV f DQG f LPSRVH FRQVWUDLQWV RQ SDUDPHWHUV W] DQG S] +HUH DJDLQ D VROXWLRQ FDQ EH REWDLQHG LQ IRUP RI D TXDUWLF SRO\QRPLDO HTXDWLRQ LQ WAWDQAf E\ HOLPLQDWLQJ k IURP (TV f DQG f DV ZH GLG HDUOLHU LQ FDVH :LWK kA NQRZQ k FDQ EH XQLTXHO\ REWDLQHG IURP (TV f DQG f DQG WKH VROXWLRQ VHW FRPSOHWHG DV XVXDO 7KLV PHWKRG SXWV DQ XSSHU ERXQG RI RQ WKH QXPEHU RI VROXWLRQ VHWV VLQFH DW PRVW IRXU GLVWLQFW YDOXHV RI 4A FDQ EH REWDLQHG IURP WKH TXDUWLF SRO\QRPLDO HTXDWLRQ LQ WA $Q HDVLHU LQYHUVH NLQHPDWLF DQDO\VLV RI WKLV VWUXFWXUH FDQ EH REWDLQHG LI WKH UROHV RI HQGHIIHFWRU IUDPH DQG EDVH IUDPH DUH UHYHUVHG DQG WKH LQWHUPHGLDWH OLQNIUDPHV DUH UHDVVLJQHG DFFRUGLQJO\ 7KLV ZLOO SXW WKH WKUHH LQWHUVHFWLQJ D[HV DW WKH HQGHIIHFWRU SRVLWLRQ LQVWHDG RI DW WKH EDVH 7KH '2) VWUXFWXUH LV VHHQ WR EH HTXLYDOHQW WR RQH WKDW KDV D D ZKLFK LV GLVFXVVHG LQ FDVH PAGE 57 :LWK WKLV DQDO\VLV ZH ILQG WKDW WKHUH FDQ EH DW PRVW WZR VROXWLRQ VHWV &DVH 7KH ILUVW WZR MRLQW D[HV LQWHUVHFW DQG WKH ODVW WZR MRLQW D[HV LQWHUVHFW 7KH UHGXFHG V\VWHP LV DD V f D&7G & UO f 7OW; 6 f DOW\ & DD & U f DO3[ 6 f DOS\ & U f U f +HUH U SRVHV D FRQVWUDLQW RQ SRVH SDUDPHWHU (TXDWLRQ f \LHOGV WZR GLVWLQFW YDOXHV RI A WKHQ (TV f DQG f ZLOO IRUP D OLQHDU V\VWHP LQ 6 DQG & ZKLFK FDQ EH VROYHG IRU D XQLTXH YDOXH RI k IRU HDFK YDOXH RI k} 7ZR VROXWLRQ VHWV DUH WKXV REWDLQHG &DVH D D 7KH LQWHUPHGLDWH WZR MRLQW D[HV LQWHUVHFW DQG WKH ODVW WZR MRLQW D[HV LQWHUVHFW 7KH UHGXFHG V\VWHP EHFRPHV DOW\ 6 DOIF[ & f &7DG & UO f FUOW[ 6 f DOW\ & DD & U f &7O3[ 6 DOS\ & U f DO3\ 6 DOS[ & Ur f (TXDWLRQV f DQG f \LHOG D XQLTXH VROXWLRQ IRU k 7KH YDOXH RI k REWDLQHGFDQ EH VXEVWLWXWHG LQ (T f RU f WR VROYH IRU & ZKLFK SURYLGHV WZR SRVVLEOH YDOXHV PAGE 58 IRU k 7KH XQXVHG HTXDWLRQ LV D FRQVWUDLQW RQ WKH HQG HIIHFWRU SRVH SDUDPHWHU W] :KHQ D RU G WKH FRQGLWLRQV IRU G+ REWDLQHG KDYH DOO EHHQ DOUHDG\ GLVFXVVHG KHQFH WKHUH DUH RQO\ WHQ PLQLPDO SRVHLQGHSHQGHQW DUP JHRPHWU\ FRQGLWLRQV IRU ZKLFK WKH UHGXFHG V\VWHP LV VLQJXODU ,Q DOO WHQ FDVHV ZH IRXQG DW PRVW WZR GLVWLQFW LQYHUVH NLQHPDWLF VROXWLRQ VHWV 7R VXPPDUL]H WKH DERYH FDVHV ZH ILQG WKDW D IRXU'2) URERW PDQLSXODWRU ZLOO LQ JHQHUDO KDYH D XQLTXH LQYHUVH NLQHPDWLF VROXWLRQ VHW $W PRVW WZR VROXWLRQ VHWV FDQ EH IRXQG ZKHQ WKH DUP KDV RQH RI WKH IROORZLQJ VSHFLDO VWUXFWXUHV 7KUHH FRQVHFXWLYH MRLQW D[HV WKDW DUH SDUDOOHO 7KUHH FRQVHFXWLYH MRLQW D[HV LQWHUVHFW 7ZR FRQVHFXWLYH SDLUV RI SDUDOOHO RU LQWHUVHFWLQJ MRLQW D[HV 7KUHH FRQVHFXWLYH MRLQW D[HV VXFK WKDW WZR LQWHUVHFW DQG WZR DUH SDUDOOHO 7KUHH FRQVHFXWLYH MRLQW D[HV VXFK WKDW WKH ILUVW WZR LQWHUVHFW DQG WKH ODVW WZR LQWHUVHFW PAGE 59 &+$37(5 62/9,1* ),9('2) 0$1,38/$7256 2QH'LPHQVLRQDO ,WHUDWLYH 7HFKQLTXH :LWK ILYH GHJUHHV RI IUHHGRP (T f WDNHV WKH IRUP $I $ $A $A $A 3 f DQG DIWHU PXOWLSO\LQJ ERWK VLGHV RI WKLV HTXDWLRQ E\ $A ZH REWDLQ A A A A 4 f ZLWK 4 $ 3 f :KHQ k LV NQRZQ PDWUL[ 4 LV IXOO\ GHWHUPLQHG DQG FDQ EH YLHZHG DV D SRVH PDWUL[ IRU D '2) DUP ZKRVH VWUXFWXUH LV GHVFULEHG E\ WKH OHIW KDQG VLGH RI (T f ZKLFK PHUHO\ H[SUHVVHV D '2) SUREOHP ,Q &KDSWHU ZH KDYH VHHQ WKDW D '2) SUREOHP FDQ DOZD\V EH VROYHG LQ FORVHGIRUP KHQFH WKH UHPDLQLQJ MRLQW YDULDEOHV FDQ EH FRPSXWHG DV VKRZQ HDUOLHU 6LQFH ZH RQO\ QHHG WR NQRZ RQH RI WKH MRLQW YDULDEOHV WR VROYH IRU WKH ZKROH VROXWLRQ VHW WKH LQYHUVH NLQHPDWLFV SUREOHP RI ILYH'2) PDQLSXODWRUV UHGXFHV WR ILQGLQJ WKH PAGE 60 YDOXH RI WKH ILUVW MRLQW YDULDEOH RQO\ DQG JHWWLQJ FORVHG IRUP YDOXHV IRU WKH UHPDLQLQJ YDULDEOHV /HW WKH FROXPQ YHFWRUV RI SRVH PDWUL[ 4 RI (T f EH 4 P F X DQG P[ F[ X[ A[ P\ F\ X\ T\ P] F] X] = L P F X T f WKHQ DQG X 5a 5 ] 5 W T 5O S 5A [ 5[ AS f f f )URP WKH OHIW KDQG VLGH RI (T f WZR YHFWRUV X/ DQG T/ FRUUHVSRQGLQJ WR YHFWRUV X DQG T DUH JLYHQ E\ 8/ 5 5 5 ] f DQG T/ B 5A5 A AA f $ QRQOLQHDU IXQFWLRQ RI A FDQ EH GHILQHG DV D GLIIHUHQFH EHWZHHQ FRUUHVSRQGLQJ TXDQWLWLHV IURP WKH OHIW DQG WKH ULJKW VLGH RI (T f )RU H[DPSOH WKH GLIIHUHQFH EHWZHHQ WKH LQQHUSURGXFWV X/T/f DQG XTf \LHOGV WKH IXQFWLRQ I kOf X/T/ XT f PAGE 61 ,I WKH YDOXH RI A XVHG WR FRPSXWH SRVH PDWUL[ 4 LQ (T f GRHV FRUUHVSRQG WR D VROXWLRQ VHW WKHQ (T f ZLOO KROG YHFWRUV X/ DQG T/ ZLOO EH H[DFWO\ HTXDO WR X DQG T UHVSHFWLYHO\ DQG IXQFWLRQ I ZLOO HTXDO ]HUR ,Q RWKHU ZRUGV VROXWLRQ VHWV RI (T f FRUUHVSRQG WR ]HURV RI IXQFWLRQ I GHILQHG LQ (T f +HQFH WKH LQYHUVH NLQHPDWLFV SUREOHP RI '2) URERW PDQLSXODWRUV UHGXFHV WR VROYLQJ WKH RQHGLPHQVLRQDO HTXDWLRQ IkLf 7KH ]HURV RI I FDQ EH IRXQG E\ XVH RI DQ\ VXLWDEOH RQHn GLPHQVLRQDO WHFKQLTXH VXFK DV 1HZWRQ5DSKVRQ RU WKH VHFDQW PHWKRG 2QFH A LV NQRZQ WKH VROXWLRQ VHW FDQ EH FRPSOHWHG E\ VROYLQJ (T f LQ FORVHG IRUP DV ZH VKRZHG LQ &KDSWHU 7KH VROXWLRQ VHW FDQ WKHQ EH FKHFNHG IRU FRQVLVWHQF\ ZLWK (T f WR GHWHUPLQH ZKHWKHU WKH RQH IRXQG LV H[WUDQHRXV RU QRW EHFDXVH WKH ]HURV RI I DUH QRW DOZD\V SDUW RI D VROXWLRQ VHW RI WKH PDQLSXODWRU &RPSXWLQJ ILkA 8VLQJ (TV f DQG f WKH LQQHUn SURGXFW X/T/ LV JLYHQ E\ 8O f O A A A r AA A AA AA n ,I ZH DSSO\ SURSHUWLHV f DQG f UHSHDWHGO\ WKLVODVW HTXDWLRQ EHFRPHV f 8MATA ] 5 fAf ]r A A AAf ]r A A A Af PAGE 62 RU DIWHU FRPSXWLQJ WKH ]FRPSRQHQWV RI WKH WHUPV LQ SDUHQWKHVHV 8/rA/ 7G G DA A f§ -GF rf 7G W 6 A AG AA D F fDU 6 DG7 & UGDA W DD A f DGD A 7G7A r f 7KLV ODVW HTXDWLRQ VKRZV WKDW k DQG k PXVW EH NQRZQ EHIRUH ZH FDQ FRPSXWH X/T/ :LWK kA NQRZQ k DQG k FDQ EH REWDLQHG E\ VROYLQJ (T f DV GHVFULEHG LQ &KDSWHU 7KH FRRUGLQDWHV RI YHFWRUV X DQG T DQG WKH LQQHUSURGXFWV XT DQG TT DUH QHFHVVDU\ IRU WKH '2) LQYHUVH NLQHPDWLF PHWKRG RI &KDSWHU (TXDWLRQ f \LHOGV 8 5A W f DOW[ 6 DOW\ & 7OW] DQG IURP (T f S[ &[ 3\ 6[ D[ T UO3[ 6 UO3\ &s DA] rO3[ 6 DO3\ & 7O3] f ZKHUH ZH KDYH DVVXPHG 5A OMBf >DMB @7 VLQFH G E\ SURSHU SRVLWLRQLQJ RI IUDPH ) PAGE 63 7KH LQQHUSURGXFWV XT DQG TT FDQ WKHQ EH HDVLO\ FRPSXWHG E\ XrT X[T[ X\T\ X]T] DQG TT T[ T\ T ZKHQ WKH QXPHULF YDOXHV RI WKH FRPSRQHQWV RI X DQG T KDYH EHHQ REWDLQHG 7KHVH LQQHU SURGXFWV FDQ EH REWDLQHG IURP (TV f DQG f DV ZHOO XT 5O Wf 5S O[ff W S O[f XT W[ S[ DA/ &[f W\ S\ D/ 6[f f DQG TT 5ALS O[f 5AWH O[f 3 /f S O[f TT SS OLO/ SO[f TT SS DA S[D[ &s S\D[ 6sf f (TXDWLRQV ff FOHDUO\ VKRZ WKDW DOO FRPSRQHQWV RI X DQG T DQG WKH LQQHUSURGXFWV XT DQG TT DUH OLQHDU IXQFWLRQV RI DQG &A D UHVXOW WKDW ZLOO SURYH XVHIXO LQ WKH QH;W VHFWLRQ 7R VXPPDUL=H Ikf@Bf FDQ EH FRPSXWHG IRU D JLYHQ YDOXH RI A DFFRUGLQJ WR WKH IROORZLQJ VWHSV 6WHS )URP WKH FXUUHQW HVWLPDWH RI A &RPSXWH WKH FRPSRQHQWV RI X DQG T DQG WKH LQQHU SURGXFWV XT DQG TT DV VKRZQ LQ (TV ff PAGE 64 6WHS &RPSXWH k DQG k IURP WKH UHGXFHG V\VWHP RI HTXDWLRQV DX\ 6 DX[ & DD 6 f &7DG & a UO f DX[ 6 DX\ & DD & U f FWF[ 6 DT\ & DD 6 U f DT\ 6 DT[ & DDG 6 DD & U f ZLWK UO TX UG GX] WWG f U WW f WX] f U UG A]f G 7G f U TTDGDGDGf £A] UGGn f GHULYHG IURP (TV ff E\ SURSHU LQGH[ VXEVWLWXWLRQ WKH LQGH[HV DUH LQFUHPHQWHG WR ILW WKH '2) SUREOHP RI (T ff 9HFWRUV X DQG T SOD\ WKH UROHV RI YHFWRUV W DQG S UHVSHFWLYHO\ 7KH ODVW V\VWHP RI HTXDWLRQV JLYHV WKH YDOXHV RI k DQG k (TXDWLRQV f DQG f ZLWK WKH SURSHU LQGH[ FKDQJHV AGf§ ADA f A DD&f & n &[ 6\ D DQG f DD&f 6 f§ &7GaWD6f & W6F[ 7&F\ n f PAGE 65 FDQ EH VROYHG IRU k $QRWKHU ZD\ WR REWDLQ LV E\ XVLQJ WKH HTXDWLRQV 6 fL X 6 & &X[ W 6 8\ f DQG DA 6 7 FFU Uf A W6X; 7&8\ D8=n f GHULYHG IURP (TV f DQG f E\ LQFUHPHQWLQJ WKH LQGH[HV :LWK k k DQG NQRZQ X/T/ FDQ EH FRPSXWHG DV LQ (T f DQG ILkAf LV WKHQ JLYHQ E\ (T f 7KH DELOLW\ WR FRPSXWH Akf ZKHQ k LV JLYHQ LV VXIILFLHQW WR LPSOHPHQW D SUDFWLFDO 1HZWRQ5DSKVRQ DOJRULWKP IRU ILQGLQJ WKH ]HURV RI IXQFWLRQ I 7KH DOJRULWKP FDQ EH SURJUDPPHG DFFRUGLQJ WR WKH IROORZLQJ VWHSV 6WHS 2EWDLQ DQ LQLWLDO HVWLPDWH IRU k $V IRU DOO LWHUDWLYH PHWKRGV WKH FORVHU WKH LQLWLDO HVWLPDWH RI k LV WR D WUXH VROXWLRQ WKH IDVWHU WKH FRQYHUJHQFH ZLOO EH ,I WKH HQGHIIHFWRU RI WKH URERW LV WUDFNLQJ D WUDMHFWRU\ JLYHQ DV D ILQLWH VHW RI HQGHIIHFWRU SRVHV D JRRG HVWLPDWH IRU ILQGLQJ WKH VROXWLRQ VHW IRU D SRVH DORQJ WKH WUDMHFWRU\ LV WKH YDOXH RI k FRUUHVSRQGLQJ WR WKH SUHFHGLQJ SRVH RQ WKH WUDMHFWRU\ 6WHS &RPSXWH k DQG k DQG WKHQ Ikf DV GHVFULEHG HDUOLHU PAGE 66 6WHS &RPSXWH WKH GHULYDWLYH GIGkA RI I ZLWK UHVSHFW WR A $ QXPHULF DSSUR[LPDWLRQ RI WKLV GHULYDWLYH LV JLYHQ E\ GIGHA >I fI 4f @64OI f ZKHUH MA LV D VPDOO LQFUHPHQW RI A 1RWH WKDW WKLV DSSUR[LPDWLRQ UHTXLUHV DQRWKHU IXQFWLRQ HYDOXDWLRQ DW AAf 6WHS 2EWDLQ D QHZ HVWLPDWH IRU A E\ WKH RQHn GLPHQVLRQDO 1HZWRQ5DSKVRQ PHWKRG LH *QHZf kL IHfGIG*f f 6WHSV WR PXVW EH UHSHDWHG XQWLO LV REWDLQHG WR WKH GHVLUHG DFFXUDF\ 7KH VROXWLRQ VHW FDQ WKHQ EH FRPSOHWHG E\ XVLQJ WKH YDOXHV RI DQG DV FRPSXWHG DW WKH ODVW LWHUDWLRQ DQG E\ FRPSXWLQJ XQLTXHO\ IURP 5B 5B 5 5 P DQG k DWDQ6&f 7KH RQHGLPHQVLRQDO PHWKRG MXVW GHVFULEHG LV IOH[LEOH LQ WHUPV RI WKH FKRLFH RI IXQFWLRQ I WR EH XVHG $ GLIIHUHQW IXQFWLRQ FDQ EH LPSOHPHQWHG 7KH RQO\ UHTXLUHPHQWV DUH WKDW IWkA EH FRPSXWDEOH IRU DQ\ YDOXH RI PAGE 67 DQG VRPH NQRZQ UHODWLRQVKLS EHWZHHQ WKH ]HURV RI I DQG WKH VROXWLRQ VHWV RI (T f )RU H[DPSOH DQRWKHU FKRLFH RI I PD\ EH IkLf T/rT/ 6nrr f RU DQ\ GLIIHUHQFH EHWZHHQ FRUUHVSRQGLQJ TXDQWLWLHV IURP WKH OHIW DQG ULJKW VLGH RI (T f 7KH IXQFWLRQ FKRLFH LV LPSRUWDQW LQ WHUPV RI PLQLPDO FRPSXWDWLRQ FRPSOH[LW\ DQG ILOWHULQJ RI H[WUDQHRXV VROXWLRQV ZKLFK DUH GLVFXVVHG QH[W ,Q DOO SUDFWLFDO H[SHULPHQWV WKH IXQFWLRQ GHILQHG LQ (T f KDV JLYHQ JRRG UHVXOWV ([WUDQHRXV VROXWLRQV $Q H[WUDQHRXV VROXWLRQ VHW LV RQH WKDW WKH LWHUDWLYH PHWKRG FRQYHUJHV WR LH LW VDWLVILHV WKH UHGXFHG V\VWHP RI HTXDWLRQV ff DQG IH[f EXW \HW LW LV QRW D VROXWLRQ IRU (T f 7KH LWHUDWLYH PHWKRG MXVW GHVFULEHG PD\ FRQYHUJH WR VXFK Dn VHW 7KLV SUREOHP ZDV DOVR UHSRUWHG E\ 7VDL DQG 0RUJDQ f ZKR GHYHORSHG D GLIIHUHQW LQYHUVH NLQHPDWLF PHWKRG WKDW PDNHV XVH RI D VLPLODU UHGXFHG V\VWHP RI HTXDWLRQV ,Q GHULYLQJ WKH UHGXFHG V\VWHP RI HTXDWLRQV f f LQ FKDSWHU YHFWRUV X DQG TDQG WKH LQQHUSURGXFWV XT DQG TT DUH WKH RQO\ SRVH UHODWHG TXDQWLWLHV WKDW ZHUH LQYROYHG 7KLV PHDQV WKDW D VROXWLRQ VHW REWDLQHG E\ FRQYHUJHQFH RI WKH PHWKRG MXVW GHVFULEHG GRHV QRW QHFHVVDULO\ VDWLVI\ RWKHU SRVH UHTXLUHPHQWV IURP (T ([WUDQHRXV VROXWLRQV FDQ EH ILOWHUHG RXW E\ D FKRLFH RI PAGE 68 IXQFWLRQ I WKDW FRQVWUDLQV PRUH RI WKH HQGHIIHFWRU SRVH HOHPHQWV DW WKH H[SHQVH RI FRPSXWDWLRQ WLPH RU E\ FKHFNLQJ DOO VROXWLRQV IRXQG IRU FRQVLVWHQF\ ZLWK RQH RU PRUH HQG HIIHFWRU SRVH HOHPHQWV ,WHUDWLQJ RQ k $Q HTXLYDOHQW RQHGLPHQVLRQDO LWHUDWLYH WHFKQLTXH FDQ EH LPSOHPHQWHG EDVHG RQ D IXQFWLRQ RI H LQVWHDG RI A 5HFDOO IURP &KDSWHU WKDW WKH KRPRJHQHRXV PDWUL[ $ GHFRPSRVHV LQWR A f§ A p ZKHUH % LV D KRPRJHQHRXV PDWUL[ IXOO\ GHWHUPLQHG E\ SDUDPHWHUV D G DQG D DQG LQGHSHQGHQW RI k 5LJKW PXOWLSOLFDWLRQ RI (T f E\ $%f \LHOGV A A A f§ a 4 f ZLWK 4 3 $% f :KHQ k LV JLYHQ PDWUL[ 4 EHFRPHV D NQRZQ SRVH PDWUL[ IRU WKH '2) SUREOHP H[SUHVVHG E\ HTXDWLRQ f 9HFWRUV Xn DQG T DUH JLYHQ E\ X 5 5JkA ] f DQG T 5 5B*Nf S nf ZKHUH LV WKH URWDWLRQ SDUW RI KRPRJHQHRXV PDWUL[% PAGE 69 % 2 2 U 2 D f U U 2 2 2 G A f§ 2 G LV WKH SRVLWLRQ YHFWRU RI % DQG 5 DQG S DUH WKH XVXDO URWDWLRQ PDWUL[ DQG SRVLWLRQ YHFWRU RI HQGHIIHFWRU SRVH 3 ([SOLFLWO\ ZH JHW DQG T Q[D 6 E[D LQ 2 E;7 X Q\D 6 E\D & UW ‘V r Q]D 6 ED & IW 1 Q[&7G E;D! 6 Q[D E[DGf & W[UG S[ Q\DG E\Df 6 f Q\D E\DGf & W\UG S\ Q]DG E]Df 6 f§ Q]D E]DGf f§ W]7G S] f f ([SUHVVLRQV RI LQQHUSURGXFWV XT DQG TT LQ WHUPV RI 6 DQG & FDQ EH REWDLQHG IURP (TV f DQG f nXT n>5n5* ]@ >5 5*Nf S@ DQG PAGE 70 TT >5 5*aNf S@ >5 5B*BNf S@ :LWK WKH XVH RI SURSHUWLHV f DQG f DV QHFHVVDU\ DQG UHDUUDQJLQJ WHUPV WKH HTXDWLRQV \LHOG XT D >QSf 6 ESf F@ UWSf G f DQG TT >DG QSf D ESf@ 6 >D QSf DG ESf@ F UG WSf D G SS f ZKHUH ZH XVHG WKH IDFW WKDW QS Q[3[ Q\3\ Q]3] ES E[3[ E\3\ E]3] WS IF[3[ W\3\ E]3] +HUH DJDLQ ZH QRWH WKDW X] S] XT DQG TT DUH OLQHDU IXQFWLRQV RI 6 DQG & :LWK WKH FRPSRQHQWV RI X DQG T DQG WKH LQQHU SURGXFWV XT DQG TT FRPSXWHG D RQHGLPHQVLRQDO LWHUDWLYH PHWKRG FDQ EH LPSOHPHQWHG DV GHVFULEHG HDUOLHU ZLWK D IXQFWLRQ Ikf JLYHQ E\ Ikf X/T/ a XT f ZKLFK ZLOO FRQYHUJH WR D YDOXH RI k PAGE 71 '2) 5RERWV ZLWK &ORVHG)RUP 6ROXWLRQ &HUWDLQ )LYHGHJUHHRIIUHHGRP URERWV ZLWK VLPSOH JHRPHWULHV PD\ \LHOG LQYHUVH NLQHPDWLF HTXDWLRQV WKDW FDQ EH VROYHG GLUHFWO\ DQG ZLWKRXW QHHG IRU D QXPHULF WHFKQLTXH VXFK DV 1HZWRQ5DSKVRQ ,Q &KDSWHU VRPH SDUWLFXODU '2) URERW VWUXFWXUHV ZHUH IRXQG IRU ZKLFK WKH UHGXFHG V\VWHP RI HTXDWLRQV ff ZDV RYHUVSHFLILHG LH WKH PDWUL[ + RI WKH OLQHDU V\VWHP ZDV VLQJXODU 7KH DQDO\VLV RI WKHVH VSHFLDO JHRPHWULHV VKRZHG WKDW RQH RU WZR RI WKH IRXU HTXDWLRQV RI WKH UHGXFHG V\VWHP EHFDPH FRQVWUDLQW HTXDWLRQV RQ SRVH HOHPHQWV SDUWLFXODUO\ HOHPHQWV WB Sf WS DQG SS ,Q WKH FDVH RI '2) URERWV WKH TXDQWLWLHV X] T XT DQG TT X SOD\LQJ WKH UROH RI W DQG T WKDW RI Sf DUH HLWKHU OLQHDU IXQFWLRQV RI DQG &A DV VKRZQ LQ (TV f f RU OLQHDU IXQFWLRQV RI DQG &A DV VKRZQ LQ (TV ff (LWKHU ZD\ WKH FRQVWUDLQW HTXDWLRQV GHVFULEHG LQ WKH WHQ FDVHV RI FKDSWHU FDQ EH XVHG WR VROYH IRU WKH FRUUHFW YDOXH RI A RU k GLUHFWO\ ZLWKRXW QHHG IRU DQ LWHUDWLYH WHFKQLTXH 7KLV UHVXOW PHDQV WKDW LI D '2) URERW PDQLSXODWRU KDV D '2) VHFWLRQ ZLWK RQH RI WKH VSHFLDO JHRPHWULHV GLVFXVVHG LQ &KDSWHU WKHQ WKH DUP FDQ EH VROYHG LQ FORVHG IRUP :H QRZ SURFHHG WR SURYH WKLV SRLQW 7KH '2) LQYHUVH NLQHPDWLFV SUREOHP RI (T f FDQ EH UHGXFHG WR WKH '2) RQH RI (T f ,Q WKLV FDVH WKH PAGE 72 UHGXFHG V\VWHP RI HTXDWLRQV ff PXVW EH VROYHG %\ VXEVWLWXWLQJ WKH H[SUHVVLRQV RI X] T] XT DQG TT IURP (TV ff LQWR (TV ff DQG UHDUUDQJLQJ ZH JHW UO AOW\ DOGr[f 6 GDOW\f & IF[3[ W\3\ f UOGW= UGU f UGn fr U &7O7W; 6 DOUW\ & 7O7W] 7Un f U DUS[ RA3\ WW3] UG G 7Gn rf DQG U fDL3\ DLG3[! 6 fDO3[ G&7O3\f & 7LG3 7GG SS DDGfDGDGf f 7KHVH ODVW IRXU HTXDWLRQV SURYH WKDW WKH WHUPV UA U U DQG U DUH DOO RI WKH IRUP UL ULO 6 UL & ULn L n f f r n n ZKHUH WKH FRQVWDQWV UAM DUH IXOO\ GHWHUPLQHG E\ WKH DUP SDUDPHWHUV DQG WKH HQGHIIHFWRU SRVH HOHPHQWV $QRWKHU FKRLFH LV WR XVH (T f 7KH UHGXFHG V\VWHP RI HTXDWLRQV LV JLYHQ E\ (TV ff ZLWK DOO HOHPHQWV RI SRVH PDWUL[ 3 UHSODFHG E\ FRUUHVSRQGLQJ HOHPHQWV RI PDWUL[ 4 RI (T f 7KH UA TXDQWLWLHV EHFRPH OLQHDU H[SUHVVLRQV LQ 6 DQG & DQG KDYH WKH IRUP PAGE 73 UL ULO V UL & ULn Ln f f f r ,QGHHG LI ZH UHSODFH X] T] XT DQG TT E\ WKHLU H[SUHVVLRQV LQ WHUPV RI 6 DQG & DV JLYHQ E\ (TV f f DQG VXEVWLWXWH LQ (TV ff VXEVWLWXWH IRU W] S] WS DQG SS DQG OHW G[ f ZH REWDLQ UO DQSf V 3f 7WSf UG f UG W f f U a7 ,HUQ] 6 U ODE] & 7 UE] WW n f U 7O&7G Q] UO DE]f 6 7 ODQ] 7 ]f & UO7 GIF] UO3=f G 7G n f DQG U >DG QSf D E A 3f 6 >D Q f3f DG E 3f F f UG WSf UG G SS D DO D G D G D G f f f ,Q WKH DQDO\VLV RI VSHFLDO IRXU '2) JHRPHWULHV &KDSWHU ZH IRXQG FDVHV ZKHUH WKH UHGXFHG V\VWHP RI HTXDWLRQV LQFOXGHG D FRQVWUDLQW RI WKH IRUP UA 6XFK D FRQVWUDLQW DSSOLHG WR RQH RI (TV ff ZLOO XVXDOO\ \LHOG D YDOXH RI A RU k ZKLFK LQ WXUQ PDNHV WKH '2) LQYHUVH NLQHPDWLFV SUREOHP VROYDEOH LQ FORVHG IRUP &DVH O 7KUHH MRLQW D[HV DUH SDUDOOHO :KHQ WKH SDUDOOHO D[HV DUH WKH ILUVW WKUHH LH D[HV DQG f (T f FDQ EH XVHG &DVH RI &KDSWHU VKRZV WKDW PAGE 74 U DQG U 7KHVH WZR FRQVWUDLQWV DQG (TV f DQG f \LHOG D V\VWHP RI HTXDWLRQV LQ 6 DQG & U 6 U & fU U 6 U & BUn ZKLFK FDQ EH VROYHG IRU k ZKHQ WKH GHWHUPLQDQW JLYHQ E\ ULU ULU A LV QRW ]HUR RWKHUZLVH WKHUH LV QR VROXWLRQ :LWK k NQRZQ WKH UHPDLQLQJ DQJOHV FDQ EH REWDLQHG LQ FORVHGIRUP ,I WKH ODVW WKUHH D[HV DUH SDUDOOHO D VLPLODU UHVXOW LV REWDLQHG E\ H[FKDQJLQJ WKH UROHV RI EDVH DQG HQGHIIHFWRU IUDPHV :KHQ WKH LQWHUPHGLDWH D[HV DUH SDUDOOHO (T f VKRXOG EH XVHG 7KH FRQVWUDLQWV U U WKHQ \LHOG D YDOXH RI A DQG WKH LQYHUVH NLQHPDWLF SUREOHP FDQ EH VROYHG LQ FORVHG IRUP DV ZHOO &DVH WZR FRQVHFXWLYH VHWV RI WZR SDUDOOHO D[HV ,I D[HV DQG DUH SDUDOOHO DQG D[HV DQG DUH SDUDOOHO (T f DQG &KDSWHU FDVH \LHOG U ZKLFK FDQ EH XVHG WR VROYH IRU k IURP (T f ,I D[HV DQG DUH SDUDOOHO DQG D[HV DQG DUH SDUDOOHO WKHQ XVLQJ (T f DQG (T f ZLOO \LHOG D YDOXH RI A &DVH 7ZR SDUDOOHO D[HV IROORZHG E\ WZR LQWHUVHFWLQJ D[HV :KHQ WKLV VSHFLDO JHRPHWU\ FRQFHUQV WKH ILUVW IRXU MRLQW D[HV RI WKH '2) DUP XVLQJ (T f DQG &KDSWHU FDVH \LHOGV U 7KLV FRQVWUDLQW DSSOLHG WR (T f JLYHV D YDOXH RI k ,I WKH XSSHU SDUW RI WKH '2) URERW PAGE 75 KDV WKH VSHFLDO VWUXFWXUH (T f FDQ EH XVHG DQG WKH FRQVWUDLQW U DSSOLHV WR (T f $QJOH A FDQ EH GLUHFWO\ FRPSXWHG &DVH 7ZR LQWHUVHFWLQJ D[HV IROORZHG E\ WZR SDUDOOHO D[HV 7KLV VWUXFWXUH FRUUHVSRQGV WR &KDSWHU FDVH +HUH WKH FRQVWUDLQW LV DQG DV LQ WKH SUHFHGLQJ FDVHV A RU k FDQ EH GLUHFWO\ FRPSXWHG IURP (T f RU f UHVSHFWLYHO\ &DVH 7KUHH LQWHUVHFWLQJ D[HV 3LHSHU f KDV VKRZQ WKDW D VL['2) PDQLSXODWRU ZLWK WKUHH LQWHUVHFWLQJ D[HV FDQ DOZD\V EH VROYHG LQ FORVHG IRUP 7KLV UHVXOW DSSOLHV WR WKH VLPSOHU FDVH RI ILYH'2) URERWV 7KLV VWUXFWXUH FRUUHVSRQGV WR FDVH RI &KDSWHU ZKHUH WKH FRQVWUDLQWV DUH U DQG U ,I WKH WKUHH LQWHUVHFWLQJ D[HV DUH WKH ILUVW WKUHH (TXDWLRQ f VKRXOG EH XVHG :LWK (TV f DQG f D YDOXH RI k FDQ EH REWDLQHG GLUHFWO\ 7KLV VDPH PHWKRG FDQ EH XVHG ZKHQ WKH ODVW WKUHH D[HV LQWHUVHFW E\ ILUVW H[FKDQJLQJ WKH UROHV RI HQGHIIHFWRU DQG EDVH IUDPHV :KHQ WKH LQWHUPHGLDWH WKUHH D[HV DUH LQWHUVHFWLQJ XVH RI (TV f f DQG f ZLOO \LHOG D YDOXH RI A &DVH 7ZR FRQVHFXWLYH VHWV RI WZR LQWHUVHFWLQJ f! D[HV 7KLV VWUXFWXUH LV DQDO\]HG LQ FDVH RI &KDSWHU 7KH FRQVWUDLQW HTXDWLRQ LV U 'HSHQGLQJ RQ ZKHUH WKLV VSHFLDO VWUXFWXUH LV ORFDWHG DORQJ WKH ILYH'2) DUP AA RU PAGE 76 k FDQ EH GLUHFWO\ FRPSXWHG E\ XVH RI (TV f RU f UHVSHFWLYHO\ ,Q WKH VSHFLDO JHRPHWULHV GHVFULEHG LQ &KDSWHU FDVHV DQG ZH GLG QRW ILQG D FRQVWUDLQW RI WKH IRUP UA \HW D ILYH'2) DUP KDYLQJ RQH RI WKHVH SDUWLFXODU JHRPHWULHV FDQ VWLOO EH VROYHG LQ FORVHG IRUP :H QRZ VWXG\ WKHVH VSHFLDO FDVHV DV WKH\ DSSO\ WR ILYHGHJUHHRIIUHHGRP URERWV &DVH 7KUHH MRLQW D[HV DUH VXFK WKDW WKH\ HLWKHU LQWHUVHFW RU WKH\ DUH SDUDOOHO WZR DW D WLPH 7KLV W\SH RI VWUXFWXUH LV VWXGLHG LQ FDVHV DQG RI &KDSWHU $VVXPLQJ WKLV JHRPHWU\ FRQFHUQV D[HV DQG RI WKH ILYH'2) DUP (T f VKRXOG EH XVHG )URP &KDSWHU FDVH DQG FDVH ZH VHH WKDW WKH ODVW WZR HTXDWLRQV RI WKH UHGXFHG V\VWHP (TV f DQG f KDYH WKH IRUP DA[ 6 \ &f U DA\ 6 T[ &A U ZKHUH T[ TA U DQG U DUH DOO OLQHDU H[SUHVVLRQV LQ DQG &A $ TXDUWLF SRO\QRPLDO HTXDWLRQ LQ WMB WDQkf LV UHDGLO\ REWDLQHG E\ VTXDULQJ DQG DGGLQJ WKH ODVW WZR HTXDWLRQV T[ T\ UD A UDfn DQG VXEVWLWXWLQJ WOWf DQG &A WAfOWMf 7KLV SRO\QRPLDO FDQ EH VROYHG IRU A DQG WKH VROXWLRQ VHW PAGE 77 FRPSOHWHG DV GHVFULEHG HDUOLHU 6LPLODUO\ IURP FDVH RI &KDSWHU ZH JHW WKH HTXDWLRQV DX\ 6 X[ &f U[ DX[ 6 X\ F! U FRUUHVSRQGLQJ WR (TVf DQG f RI WKH UHGXFHG V\VWHP RI HTXDWLRQV +HUH DJDLQ D TXDUWLF SRO\QRPLDO HTXDWLRQ LQ WA LV REWDLQHG E\ HOLPLQDWLQJ 6 DQG & :KHQ WKH WKUHH D[HV ZLWK WKH VSHFLDO JHRPHWU\ DUH ORFDWHG HOVHZKHUH DORQJ WKH ILYH'2) VWUXFWXUH D VLPLODU UHVXOW FDQ EH REWDLQHG E\ XVLQJ HTXDWLRQ f RU E\ H[FKDQJLQJ WKH UROHV RI EDVH DQG HQGHIIHFWRU IUDPHV 7R VXPPDUL]H WKH DERYH FDVHV ZH ILQG WKDW D '2) URERW PDQLSXODWRU ZLOO DOORZ FORVHGIRUP VROXWLRQV LI DQ\ RI WKH IROORZLQJ FRQGLWLRQV LV VDWLVILHG 7KUHH FRQVHFXWLYH MRLQW D[HV DUH SDUDOOHO 7KUHH FRQVHFXWLYH MRLQW D[HV LQWHUVHFW 7KHUH DUH WZR FRQVHFXWLYH VHWV RI WZR MRLQW D[HV WKDW DUH HLWKHU SDUDOOHO RU LQWHUVHFWLQJ 7KUHH FRQVHFXWLYH MRLQW D[HV DUH VXFK WKDW WZR LQWHUVHFW DQG WZR DUH SDUDOOHO 7KUHH FRQVHFXWLYH MRLQW D[HV DUH VXFK WKDW WKH ILUVW WZR LQWHUVHFW DQG WKH ODVW WZR LQWHUVHFW 1RWH WKDW WKHVH FRQGLWLRQV DUH QRW H[FOXVLYH RI RQH DQRWKHU )RU H[DPSOH DUPV WKDW VDWLVI\ FRQGLWLRQ LQFOXGH WKRVH WKDWVDWLVI\ FRQGLWLRQ ‘ PAGE 78 &+$37(5 62/9,1* 6,;'2) 0$1,38/$7256 5HGXFWLRQ WRD '2) 3UREOHP $W OHDVW VL[ GHJUHHV RI IUHHGRP DUH UHTXLUHG IRU D URERW PDQLSXODWRU WR EH DEOH WR DUELWUDULO\ SRVLWLRQ DQG RULHQW LWV HQGHIIHFWRU ZLWKLQ LWV ZRUNVSDFH (TXDWLRQ f ZLWK Q HTXDO WR VL[ \LHOGV $L $ $ $ $J $J 3 f ,I ERWK VLGHV RI WKLV HTXDOLW\ DUH PXOWLSOLHG E\ $MA $f WKH HTXDWLRQ EHFRPHV $ $ $J $J f§ 4 f ZLWK 4 $ $ 3 f :KHQ k DQG k DUH NQRZQ PDWUL[ 4 LV IXOO\ GHWHUPLQHG DQG FDQ EH YLHZHG DV D SRVH PDWUL[ IRU D '2) DUP ZKRVH VWUXFWXUH LV GHVFULEHG E\ WKH OHIW KDQG VLGH RI (T f ZKLFK PHUHO\ H[SUHVVHV D '2) SUREOHP ,Q &KDSWHU ZH KDYH VHHQ WKDW D '2) SUREOHP FDQ DOZD\V EH VROYHG LQ FORVHGIRUP KHQFH WKH UHPDLQLQJ MRLQW YDULDEOHV FDQ EH FRPSXWHG IURP (T f PAGE 79 )LUVW ZH VKRZ WKDW D VLPLODU UHVXOW FDQ EH REWDLQHG LI k DQG k DUH NQRZQ RU LI kA DQG k DUH NQRZQ LQVWHDG RI WKH ILUVW WZR MRLQW YDULDEOHV ,Q WKH GHYHORSPHQW RI WKH '2) LQYHUVH NLQHPDWLFV VROXWLRQ ZH KDYH XVHG WKH VLPSOLI\LQJ DVVXPSWLRQ WKDW WKH ODVW IUDPH KDG '+SDUDPHWHUV G D DQG D DOO HTXDO WR ]HUR $OWKRXJK WKLV DVVXPSWLRQ LV REYLRXVO\ FRUUHFW LQ WKH FDVH RI (T f ZH PXVW VKRZ WKDW LW FDQ EH REWDLQHG LQ RWKHU FDVHV $V VKRZQ LQ (T f D KRPRJHQHRXV PDWUL[ $A GHFRPSRVHV LQWR $A $A ZKHUH $A DQG DUH JLYHQ E\ (TV f DQG f DQG $A LV D KRPRJHQHRXV PDWUL[ IRU ZKLFK '+ SDUDPHWHUV D G DQG D DUH ]HUR ,I WKH YDOXHV RI kA DQG k DUH NQRZQ (TXDWLRQ f QRZ UHGXFHV WR WKH '2) SUREOHP $ $ $ f§ 4 f ZKHUH 4 $O 3 $ %B f 6LPLODUO\ ,I k DQG k DUH NQRZQ WKH LQYHUVH NLQHPDWLF WDVN EHFRPHV WKDW RI VROYLQJ WKH '2) FDVH $ $ $ f§ a f ZLWK 4 3 $J $ f ,Q WKH IROORZLQJ VHFWLRQ ZH ZLOO VKRZ KRZ D WZR GLPHQVLRQDO LWHUDWLYH WHFKQLTXH FDQ EH LPSOHPHQWHG WR VROYH WKH LQYHUVH NLQHPDWLFV SUREOHP RI VL['2) URERW PAGE 80 PDQLSXODWRUV $OWKRXJK WKLV WHFKQLTXH FDQ HTXDOO\ EH GHYHORSHG XVLQJ (TV f RU f LW ZLOO EH EDVHG RQ (T f IRU FRQYHQLHQFH 7ZR'LPHQVLRQDO ,WHUDWLYH 7HFKQLTXH 6LQFH ZH RQO\ QHHG WR NQRZ RI WKH MRLQW YDULDEOHV WR VROYH IRU WKH ZKROH VROXWLRQ VHW WKH LQYHUVH NLQHPDWLFV SUREOHP RI VL['2) PDQLSXODWRUV FDQ EH UHGXFHG WR ILQGLQJ WKH YDOXHV RI WKH ILUVW WZR MRLQW YDULDEOHV RQO\ DQG JHWWLQJ FORVHGIRUP YDOXHV IRU WKH UHPDLQLQJ YDULDEOHV $ QXPHULFDO WHFKQLTXH DLPHG DW ILQGLQJ WKH YDOXHV RI 4MA DQG FDQ EH LPSOHPHQWHG E\ GHILQLQJ D V\VWHP RI WZR QRQOLQHDU HTXDWLRQV LQ A DQG If f JkOf f WKDW FDQ EH VROYHG XVLQJ DQ LWHUDWLYH PHWKRG VXFK DV D WZR GLPHQVLRQDO 1HZWRQ5DSKVRQ )URP WKH OHIW KDQG VLGH RI (T f WZR YHFWRUV X/ DQG T/ FRUUHVSRQGLQJ WR YHFWRUV X DQG T YHFWRUV X DQG T UHODWH WR SRVH 4 DV VKRZQ LQ (T ff DUH JLYHQ E\ 8/ 5 U U ] f AA A L f  f f DQG PAGE 81 :H GHILQH WZR QRQOLQHDU IXQFWLRQV RI A DQG k DV GLIIHUHQFHV EHWZHHQ WKH LQQHUSURGXFWV XATA TATA DQG WKH LQQHUSURGXFWV XT DQG TT UHVSHFWLYHO\ IAkf XOrA/ f§ ff Jkf T/T/ TT f ,I WKH YDOXHV RI MB DQG k XVHG WR FRPSXWH SRVH PDWUL[ 4 LQ (T f GR FRUUHVSRQG WR D VROXWLRQ VHW WKHQ (T f ZLOO KROG DQG YHFWRUV X/ DQG T/ ZLOO EH H[DFWO\ HTXDO WR X DQG T IRUFLQJ ERWK IXQFWLRQV I DQG J WR EH HTXDO WR ]HUR ,Q RWKHU ZRUGV VROXWLRQ VHWV RI (T f FRUUHVSRQG WR ]HURV RI WKH IXQFWLRQV I DQG J GHILQHG LQ (TV f DQG f &RPSXWLQJ II4A42 DQG TI4A4Rf ,Q RUGHU WR FRPSXWH WKH YDOXHV RI I DQG J IRU D JLYHQ SDLU Akf WKH FRPSRQHQWV RI YHFWRUV X T DQG WKH LQQHU SURGXFWV XT DQG TT DUH QHHGHG WR VROYH WKH '2) HTXDWLRQ f ZKLFK LQ WXUQ DOORZV FRPSXWDWLRQ RI LQQHU SURGXFWV 8/r DQG T/T/ DQG ILQDOO\ WKH YDOXHV RI I DQG J 9HFWRUV X DQG T FRPSXWHG IURP (T f DUH X 5B UA 5 ] UB 5B W f DQG T 5B >5I S O[f @ f ,I ZH FRQVLGHU WKH FRPSRQHQWV RI YHFWRU W DV H[SUHVVHG ZLWK UHVSHFW WR IUDPH )A PAGE 82 ;W[ & IF[ 6 IF\ OIF< W 7OVO IF[ 7OFO IF\ rO IF] OW] DO6O IF[ a DOFO 3\ 7 W] WKHQ YHFWRU X LV JLYHQ E\ X 9 [W & ;W[ 6 W\ W6 ;W[ W& A\ D D6 OIF[ D& OIF\ 7 f 7R REWDLQ WKH FRPSRQHQWV RI YHFWRU T ILUVW ZH UHZULWH (T f DV T A A5O 3 f A ALf a A A A DQG ZH GHILQH K ;3[ OS\ 5rf S & 3[ 6 3\ 7OVO 3[ 7OFO 3\ DO 3] B 9 DOVO 3[ DOFO 3\ 7 3] YHFWRU T LV WKHQ JLYHQ E\ T & ;3[ DOf 6 ;3\ D 76 ;3[ 7& ;3\ II A] DG D6 ;3[ D& 3\ U A] a 7G f 7KH LQQHU SURGXFW XT FDQ EH GHULYHG IURP (TV f DQG f XT 5A 5I Wf paUa W3 a ;Lf a 5nL @f PAGE 83 8VLQJ f DQG f DV QHHGHG DQG H[SDQGLQJ \LHOGV XT W S f§ Af f§ AW RU XT WS WO WO ZKLFK JLYHV XT WS & 6 D W[ & D W\ 6 G W] f 6LPLODUO\ WKH VTXDUH RI WKH OHQJWK RI YHFWRU T TT LV JLYHQ E\ TT 5f5L >S LOfr A r UaU W3 A f§ f§ ZKHUH ZH IDFWRUHG RXW 5 5A P WKH H[SUHVVLRQ RI T IURP (T f 8VLQJ f DQG f DQG H[SDQGLQJ DJDLQ OHDGV WR TT SS AA m f§ S 5A S 5A A Amf RU TT D >D/ S[f & S\ 6@ G S D SS Ds D G f (TXDWLRQ f JLYHV ULVH WR D UHGXFHG V\VWHP VLPLODU WR WKDW RI (TV ff ZLWK WKH UHTXLUHG VKLIW LQ LQGH[HV DX\ 6 DX[ & DD 6 FUDG & UA f &78; A f DX\ r &A U f PAGE 84 &7T[ 6 f DT\ & f DD 6 U DT\ 6 DT[ & FUDG 6 DD & U ZLWK U/ TX UG GX] UUG U WW UX] U UG T]f G UG W TT D G D G D G n 7GG f 6ROYLQJ WKLV V\VWHP RI HTXDWLRQV ZLOO \LHOG WKH YDOXHV RI DQG k 7KH YDOXH RI FDQ WKHQ EH FRPSXWHG IURP WKH WZR HTXDWLRQV AGa7DAA A DDAnf FT[ 6T\ D f DQG DDJ&Jf 6 f§ FUFAfD6f & UVT[ n&T\ DT]aGf f f GHULYHG IURP (TV f DQG f RU IURP WKH HTXDWLRQV U r Ar 7 f A W AA A a A8; 6X\ f DQG &7A A f§ 7Dar7 f A W6X[ U&X\ FUX] FRUUHVSRQGLQJ WR (TV f DQG f f f f f f f f f PAGE 85 :H FDQ QRZ FRPSXWH WKH LQQHU SURGXFWV X/T/ DQG T/T/ %\ LQFUHPHQWLQJ WKH LQGH[HV LQ (T f ZH GHULYH 8/r 7G D&7 6 &7GD & 7G FU 6 D & DG 6f a D A DU A DGU A 7GDf A D&7 A f FGF r 7G7fr f 9HFWRU T/ REWDLQHG IURP WKH OHIW KDQG VLGH RI (T f LV AA AnAfO f DQG WKH VTXDUH RI LWV OHQJWK LV JLYHQ E\ 6O6O AA A Af Af f AA ,f ,f RU a A AA A AAf f AA AAA A Af! DIWHU IDFWRULQJ RXW 5 5f DQG XVLQJ LQQHU SURGXFW LQYDULDQFH RI URWDWLRQV 0XOWLSO\LQJ RXW WKH WHUPV LQ SDUHQWKHVHV DQG XVLQJ f DQG f ZKHUH QHFHVVDU\ WKH ODVW HTXDWLRQ \LHOGV WD &AD D & DG 6A D 6DU6 DGU & UGD DGf GJ WG DD 6 f§ FUGD & G7Uf DD A eAD A UAG@ D GA D G DA GV f PAGE 86 *LYHQ D SDLU k kf WKH FRUUHVSRQGLQJ YDOXHV RI Ikkf DQG Jkkf DUH REWDLQHG E\ WKH IROORZLQJ VWHSV 6WHS )RU LQLWLDO YDOXHV RI k DQG k FRPSXWH WKH FRRUGLQDWHV RI YHFWRUV X DQG T DV JLYHQ E\ (TV f DQG f 7KH LQQHU SURGXFWV XT DQG TT FDQ EH FRPSXWHG XVLQJ WKH UHJXODU LQQHU SURGXFW IRUPXOD XT X[T[ X\T\ X]T] DQG TT T[ T\ T] 6WHS 6ROYH WKH UHGXFHG V\VWHP RI (TV ff IRU k DQG k 6WHS &RPSXWH WKH YDOXH RI k IURP (TV f DQG f RU (TV f DQG f 6WHS &RPSXWH WKH LQQHU SURGXFWV XATA DQG T/T/ JLYHQ E\ (TV f DQG f UHVSHFWLYHO\ DQG FRPSXWH WKH YDOXHV RI I DQG J DV JLYHQ E\ (TV f DQG f 7ZR'LPHQVLRQDO 1HZWRQ5DSKVRQ 7KH ]HURV RI I DQG J FDQ EH LWHUDWLYHO\ FRPSXWHG DQG FKHFNHG IRU FRQVLVWHQF\ ZLWK (T f ,I D FRPSXWHU SURJUDP IRU HYDOXDWLQJ WKH WZR IXQFWLRQV LV DYDLODEOH WKH SDUWLDO GHULYDWLYHV RI I DQG J ZLWK UHVSHFW WR k DQG k GHQRWHG IOI I DQG JOI J UHVSHFWLYHO\ FDQ EH QXPHULFDOO\ DSSUR[LPDWHG E\ IOkOf GIDH/ >I k kfI kf @ f PAGE 87 IpLLpfa %IDk >IkkfIkf@k f DQG LpLpf %Jk >JfJf@k f Jkf DJDk &JkfJkHf@mk f ZKHUH DQG k DUH VPDOO LQFUHPHQWV RI k DQG UHVSHFWLYHO\ 7KH WZRGLPHQVLRQDO 1HZWRQ5DSKVRQ WHFKQLTXH IRU VROYLQJ WKH LQYHUVH NLQHPDWLFV SUREOHP IRU D VL[UHYROXWH '2) URERW DUP RI DUELWUDU\ DUFKLWHFWXUH SURFHHGV DFFRUGLQJ WR WKH IROORZLQJ VWHSV 6WHS $VVXPH DQ LQLWLDO HVWLPDWH RI k DQG k DQG FRPSXWH k k DQG k 6WHS )URP WKH YDOXHV RI k k k k DQG k FRPSXWH Ikkf DQG Jkf DV LQ (TV f DQG f 6WHS &RPSXWH WKH SDUWLDO GHULYDWLYHV RI I DQG J ZLWK UHVSHFW WR k DQG k E\ QXPHULF DSSUR[LPDWLRQV DV VKRZQ HDUOLHU 6WHS 2EWDLQ D QHZ HVWLPDWH IRU k DQG k E\ WKH WZRGLPHQVLRQDO 1HZWRQ5DSKVRQ PHWKRG LH HO p I I IkHf B B J[ J B JIkf QHZ 6WHS 5HSHDW VWHSV WR XQWLO GHVLUHG DFFXUDF\ LV DWWDLQHG PAGE 88 6WHS &RPSOHWH WKH VROXWLRQ VHW E\ XQLTXHO\ FRPSXWLQJ k IURP r f & Q; 5 [ 6 f§ 7f S f S % a S f N N N N N Q\ B Q] B 6WHS &KHFN WKH VROXWLRQ VHW IRU FRQVLVWHQF\ ZLWK (T f &KRLFH RI IXQFWLRQV I DQG J 7KH IXQFWLRQV I DQG J GHILQHG E\ (TV f DQG f DUH FRPSXWDWLRQDOO\ HFRQRPLFDO VLQFH WKH\ GR QRW UHTXLUH FRPSXWDWLRQ RI WKH IRUZDUG NLQHPDWLFV RU WKH LQYHUVH MDFRELDQ RI WKH PDQLSXODWRU ,Q IDFW HYHQ WKH YDOXH RI H LV QRW UHTXLUHG WR FRPSXWH I DQG J VLQFH (T f LV FRQVLGHUHG RQO\ DIWHU FRQYHUJHQFH 8QIRUWXQDWHO\ D SDLU A f IRU ZKLFK ERWK I DQG J DUH ]HUR LV QRW JXDUDQWHHG WR FRUUHVSRQG WR D VROXWLRQ VHW RI (T f ([WUDQHRXV VROXWLRQ VHWV FDQ EH FRQYHUJHG WR DV ZHOO 7KHVH DUH MRLQW YDOXHV WKDW ZLOO \LHOG DQ HQGHIIHFWRU SRVH WKDW LV QRW H[DFWO\ WKH GHVLUHG RQH 2WKHU IXQFWLRQV WKDW IXOO\ FRQVWUDLQW WKH HQGHIIHFWRU SRVH FDQ EH GHILQHG DW WKH FRVW RI JUHDWHU FRPSXWDWLRQDO FRPSOH[LW\ :X DQG 3DXO f KDYH VKRZQ WKDW WKH GLIIHUHQFH EHWZHHQ DFWXDO DQG GHVLUHG HQGHIIHFWRU SRVHV FDQ EH H[SUHVVHG DV D [ YHFWRU [H JLYHQ E\ PAGE 89 ; Q/ r 3 f 3OA [ E/ r 3 3/f [ E/ f 3 3O! [ W/E WE/f [ Q/W QW/f B [ E/Q EQ/f f ZKHUH QI E W DQG S DUH WKH YHFWRUV WKDW GHVFULEH WKH GHVLUHG HQGHIIHFWRU SRVH 3 DV GHILQHG LQ f DQG YHFWRUV Q/n E/n IF/n DQFA 3/ DUH WAHLU FRUUHVSRQGLQJ YHFWRUV IURP WKH OHIW KDQG VLGH RI HTXDWLRQ f 7ZR IXQFWLRQV FDQ EH GHILQHG DV IHkf [A [ [ f Jf [ [ [ f $ SDLU f WKDW LV D ]HUR RI ERWK I DQG J LV JXDUDQWHHG WR FRUUHVSRQG WR D VROXWLRQ VHW RI (T f VR WKDW WKH LWHUDWLYH PHWKRG GHVFULEHG DERYH ZLOO RQO\ FRQYHUJH WR D WUXH VROXWLRQ +RZHYHU QRZ WKH IRUZDUG NLQHPDWLFV PXVW EH FRPSXWHG DW HDFK LWHUDWLRQ VLQFH WKH FRPSRQHQWV RI YHFWRUV Q/n E/n A/n DQFA "O DUH DOO QHHGHG WR HYDOXDWH IXQFWLRQV I DQG J DV GHILQHG E\ (TV f DQG f PAGE 90 2QH'LPHQVLRQDO 0HWKRG 7KH LQYHUVH NLQHPDWLF SUREOHP IRU VL['2) PDQLSXODWRUV UHGXFHV WR D ILYH'2) RQH ZKHQ WKH ILUVW RU WKH ODVW MRLQW YDULDEOH LV NQRZQ (TXDWLRQ f EHFRPHV $ $ $ $ $ n f ZLWK 4 $O 3 f ZKHQ kL LV NQRZQ DQG $L A A A 4 f ZLWK 4 3 $JAJ f LI kJ LV NQRZQ ,Q ERWK FDVHV D ILYH'2) SUREOHP LV REWDLQHG :KHQ WKH UHVXOWLQJ ILYH'2) SUREOHP LV VROYDEOH LQ FORVHG IRUP NQRZOHGJH RI kA RU k LV WKHQ VXIILFLHQW WR \LHOG D FRPSOHWH VROXWLRQ VHW 7KH LQYHUVH NLQHPDWLF SUREOHP WKHQ UHGXFHV WR ILQGLQJ RQH MRLQW DQJOH ZKLFK FDQ EH DFFRPSOLVKHG E\ D RQHGLPHQVLRQDO LWHUDWLYH WHFKQLTXH ,Q FKDSWHU ZH IRXQG WKDW D VXIILFLHQW FRQGLWLRQ IRU FORVHG IRUP VROXWLRQV RI '2) PDQLSXODWRUV LV WKDW WKH\ KDYH RQH RI WKH VSHFLDO VWUXFWXUHV OLVWHG DW WKH HQG RI &KDSWHU 6L['2) DUPV WKDW LQFOXGH D ILYH'2) VHJPHQW ZLWK WKLV W\SH RI JHRPHWU\ FDQ WKHQ EH VROYHG XVLQJ D RQHn GLPHQVLRQDO LWHUDWLYH PHWKRG 7KLV LWHUDWLYH WHFKQLTXH FDQ EH LPSOHPHQWHG LQ PXFK WKH VDPH ZD\ DV GHVFULEHG LQ &KDSWHU PAGE 91 IRU ILYHGHJUHHRIIUHHGRP DUPV $VVXPLQJ (T f LV WR EH VROYHG ZH GHILQH D IXQFWLRQ I RI MA E\ IOf 8OA/ n X n n f ZKHUH YHFWRUV X/ T/ X DQG T DUH GHILQHG DV HDUOLHU *LYHQ D YDOXH RI A YHFWRUV X DQG T DUH FRPSXWHG IURP (T f WKH YDOXHV RI WKH UHPDLQLQJ MRLQW YDULDEOHV DUH FRPSXWHG LQ FORVHG IRUP IURP (T f DV LQGLFDWHG LQ &KDSWHU DQG $SSHQGL[ % WKH LQQHU SURGXFW X/T/ FDQ WKHQ EH REWDLQHG DV LQ (T f ZLWK WKH SURSHU LQGH[ DGMXVWPHQWV DQG WKH YDOXH RI I LV WKHQ JLYHQ E\ (T f $V ZH KDYH VHHQ EHIRUH WKH DELOLW\ WR FRPSXWH WKH IXQFWLRQ I IRU D JLYHQ YDOXH RI A DOORZV WKH LPSOHPHQWDWLRQ RI D SUDFWLFDO RQHGLPHQVLRQDO 1HZWRQ5DSKVRQ DOJRULWKP 7KHUHIRUH ZH FDQ FRQFOXGH WKDW D VL[GHJUHHRIIUHHGRP PDQLSXODWRU ZLWK WZR FRQVHFXWLYH SDLUV RI LQWHUVHFWLQJ RU SDUDOOHO MRLQW D[HV RU WKUHH FRQVHFXWLYH MRLQW D[HV WKDW DUH SDUDOOHO DQGRU LQWHUVHFWLQJ WZR DW D WLPH FDQ EH VROYHG E\ XVH RI D RQHGLPHQVLRQDO LWHUDWLYH WHFKQLTXH LQVWHDG RI WKHn WZRGLPHQVLRQDO PHWKRG UHTXLUHG IRU DQ DUP RI DUELWUDU\ DUFKLWHFWXUH &ORVHG)RUP 6ROXWLRQ 6RPH VL[GHJUHHRIIUHHGRP PDQLSXODWRUV ZLWK VLPSOH JHRPHWULHV GR QRW UHTXLUH DQ\ LWHUDWLYH PHWKRG VLQFH WKH\ FDQ EH VROYHG LQ FORVHGIRUP 3LHSHU f KDV VKRZQ WKDW PAGE 92 D VXIILFLHQW FRQGLWLRQ IRU FORVHGIRUP VROXWLRQV LV WKDW WKUHH FRQVHFXWLYH D[HV EH LQWHUVHFWLQJ 7KH LQYHUVH NLQHPDWLFV SUREOHP WKHQ UHGXFHV WR ILQGLQJ WKH ]HURV RI D TXDUWLF SRO\QRPLDO ,Q WKH OLWHUDWXUH ,W VHHPV WR EH FRPPRQ NQRZOHGJH WKDW WKUHH FRQVHFXWLYH MRLQW D[HV WKDW DUH SDUDOOHO LV DQRWKHU VXIILFLHQW JHRPHWULF FRQGLWLRQ IRU FORVHG IRUP VROXWLRQV 7KH DQDO\VLV RI &KDSWHU DQG $SSHQGL[ $ VKRZHG WKDW XQGHU FHUWDLQ FRQGLWLRQV WKH UHGXFHG V\VWHP RI HTXDWLRQV ff LQFOXGHG FRQVWUDLQW HTXDWLRQV RI WKH IRUP U f 7KH TXDQWLWLHV UA L O DUH IXQFWLRQV RI kAA DQG k DV ZH KDYH VHHQ HDUOLHU %\ ORRNLQJ IRU FRQGLWLRQV XQGHU ZKLFK D MRLQW YDULDEOH YDOXH FDQ EH GLUHFWO\ REWDLQHG IURP DQ HTXDWLRQ KDYLQJ WKH IRUP RI (T f ZH ILQG WZR PRUH VXIILFLHQW VL['2) URERW VWUXFWXUH FRQGLWLRQV IRU FORVHGIRUP VROXWLRQV H[FOXGLQJ WKH DOUHDG\ NQRZQ FRQGLWLRQV RI WKUHH SDUDOOHO RU WKUHH LQWHUVHFWLQJ D[HVf :KHQ WKH ILUVW WZR MRLQW D[HV RI D PDQLSXODWRU DUH SDUDOOHO VR WKDW A WKHQ FU A DQG WKH ]FRPSRQHQWV RI YHFWRUV X DQG T JLYHQ E\ (TV f DQG f EHFRPH X] D W\ & IF[ 6 f 7LW] f T] D 3[ 6 3\ &f U 3]fGf f DQG PAGE 93 7KLV VKRZV WKDW U DQG U DV JLYHQ LQ f DQG f EHFRPH OLQHDU IXQFWLRQV RI 6 DQG FLf :KHQ MRLQW D[HV DQG DUH SDUDOOHO DQG MRLQW D[HV DQG DUH SDUDOOHO WKH UHGXFHG V\VWHP RH HTXDWLRQV f f EHFRPHV VLPLODU WR WKDW RI FDVH RI &KDSWHU DX\ 6 DX[ & f U f DD 6 U f DA\ 6 D[ & &7DG 6 DD & Un f (TXDWLRQ f \LHOGV WZR SRVVLEOH YDOXHV IRU kn HDFK RI ZKLFK ZLOO SURYLGH WZR SRVVLEOH YDOXHV RI k IURP (T f ZKHQ VXEVWLWXWHG LQ WKH H[SUHVVLRQ RI U 7KH UHPDLQLQJ MRLQW YDOXHV FDQ WKHQ EH FRPSXWHG LQ FORVHG IRUP $ VLPLODU GHYHORSPHQW RFFXUV ZKHQ D[HV DQG DUH SDUDOOHO DQG D[HV DQG LQWHUVHFW 7R VXPPDUL]H D VL['2) PDQLSXODWRU KDV D FORVHGIRUP VROXWLRQ LI RQH RI WKH IROORZLQJ FRQGLWLRQV LV VDWLVILHG 7KUHH FRQVHFXWLYH MRLQW D[HV DUH SDUDOOHO 7KUHH FRQVHFXWLYH MRLQW D[HV LQWHUVHFW DW RQH SRLQW 7KH DUP LV IRUPHG RI WKUHH VHWV RI WZR SDUDOOHO D[HV 7KLV VWUXFWXUH LV LOOXVWUDWHG LQ )LJXUH Df 7KH DUP KDV WZR VHWV RI WZR SDUDOOHO MRLQW D[HV IROORZHG RU SUHFHGHG E\ WZR LQWHUVHFWLQJ D[HV 7KHVH VWUXFWXUHV DUH LOOXVWUDWHG LQ )LJXUH Ef DQG Ff PAGE 94 E SDLUV RI SDUDOOHO MRLQW D[HV IROORZHG E\ LQWHUVHFWLQJ MRLQW D[HV F SDLUV RI SDUDOOHO MRLQW D[HV SUHFHGHG E\ LQWHUVHFWLQJ MRLQW £[HV )LJXUH '2) PDQLSXODWRUV ZLWK FORVHGIRUP LQYHUVH NLQHPDWLFV PAGE 95 &+$37(5 257+2*21$/ 0$1,38/$7256 'HILQLWLRQ $Q QD[HV VHULDO NLQHPDWLF FKDLQ RI UHYROXWH RU SULVPDWLF MRLQWV LV RUWKRJRQDO LI DOO WZLVW DQJOHV D L O Q DORQJ WKH FKDLQ DUH RU LU $Q RSHQ RUWKRJRQDO NLQHPDWLF FKDLQ ZLOO EH FDOOHG DQ RUWKRJRQDO PDQLSXODWRU 'RW\ f 6L['2) RUWKRJRQDO PDQLSXODWRUV FDQ EH FODVVLILHG LQ WHUPV RI WKH YDOXHV RI WKHLU WZLVW DQJOHV DA L O 7ZLVW DQJOH D LV DOZD\V DVVXPHG WR EH ]HUR LQ WKLV WH[W ,Q IDFW WKH YDOXH RI DJ FDQ EH FKRVHQ DUELWUDULO\ VLQFH ]J LV QRW D MRLQW D[LV 7KHUHIRUH WKHUH DUH RQO\ GLVWLQFW FODVVHV RI RUWKRJRQDO PDQLSXODWRUV DV OLVWHG LQ 7DEOH RI ZKLFK KDYH RU PRUH DGMDFHQW SDUDOOHO MRLQW D[HV ZKLFK UHGXFHV WKHLU FDSDELOLW\ WR OHVV WKDQ VL[ GHJUHHV RI IUHHGRP $V D UHVXOW WKHUH DUH RQO\ W\SHV RI VL[MRLQW RUWKRJRQDO PDQLSXODWRUV ZLWK IXOO VSDWLDO SRVLWLRQ DQG RULHQWDWLRQ FDSDELOLW\ $ FRQYHQLHQW QRWDWLRQ IRU WKLV FODVVLILFDWLRQ RI RUWKRJRQDO PDQLSXODWRUV LV REWDLQHG E\ DVVLJQLQJ D ELW ELQDU\ QXPEHU WR HDFK RI WKHVH W\SHV LQ ZKLFK ELW L LV LI re DQG ELW L LV LI DA Q )RU H[DPSOH D PDQLSXODWRU ZLWK WZLVW DQJOHV PAGE 96 D U D WW D DQG R/ U EHORQJV WR WKH FODVV RI RUWKRJRQDO PDQLSXODWRUV 6LQFH PRVW LQGXVWULDO URERW DUPV DUH RUWKRJRQDO LW LV ZRUWKZKLOH WR FRQVLGHU WKH LQYHUVH NLQHPDWLFV SUREOHP ZLWK UHVSHFW WR WKHVH PDQLSXODWRUV 7KH $PDWULFHV DVVRFLDWHG $LD f RU $LD Uf KDYH RQH RI WKH FL 6L DL&L VL &L DL6L GL &L VL DLFL 6L FL DLVL f f )XUWKHU FRPSXWDWLRQDO VLPSOLILFDWLRQ LV REWDLQHG LQ WKH LQYHUVH NLQHPDWLF HTXDWLRQV ZLWK RUWKRJRQDO PDQLSXODWRUV VLQFH 5A] 5MB] ] LI DA DQG f f§n ‘ n n f B 5A] \ LI DA Z 'RW\ f KDV VKRZQ WKDW RI WKH FODVVHV RI QRQWULYLDO RUWKRJRQDO PDQLSXODWRUV WKRVH ZLWK QRQ]HUR PAGE 97 WZLVW DQJOHV FODVVHV DQG f KDYH FORVHGIRUP VROXWLRQV 7KH LQYHUVH NLQHPDWLF DQDO\VLV RI &KDSWHU VKRZV WKDW WKH PRVW FRPSOH[ VL['2) URERW VWUXFWXUH FDQ EH VROYHG E\ XVH RI D WZRGLPHQVLRQDO LWHUDWLYH WHFKQLTXH 6LPSOHU VWUXFWXUHV RQO\ UHTXLUH D RQHn GLPHQVLRQDO QXPHULFDO WHFKQLTXH DQG VRPH HYHQ VLPSOHU VWUXFWXUHV FDQ EH VROYHG LQ FORVHGIRUP ,Q 7DEOH ZH SURYLGH D OLVW RI DOO WKLUW\WZR RUWKRJRQDO PDQLSXODWRU FODVVHV LQ ZKLFK ZH LQGLFDWH WKH GHJHQHUDWH JHRPHWULHV DQG IRU WKH WZHQW\ IRXU QRQn GHJHQHUDWH FODVVHV ZH LQGLFDWH D VXLWDEOH LQYHUVH NLQHPDWLF PHWKRG QHFHVVDU\ IRU VROYLQJ WKH PRVW FRPSOH[ DUP VWUXFWXUH ZLWKLQ WKDW FODVV ,W PXVW EH XQGHUVWRRG WKDW LQWHUVHFWLQJ D[HV FDQQRW EH FRQVLGHUHG DFFRUGLQJ WR D FODVVLILFDWLRQ EDVHG RQ WKH YDOXHV RI WKH WZLVW DQJOHV DORQH 7KH FKRLFH RI LQYHUVH NLQHPDWLF PHWKRG LQGLFDWHG LQ 7DEOH LV EDVHG VROHO\ RQ WKH SUHVHQFH RI SDUDOOHO D[HV ZLWKLQ D JLYHQ FODVV 6LPSOHU LQYHUVH NLQHPDWLF PHWKRGV FDQ EH XVHG LI DQ\ RI WKH VSHFLDO VWUXFWXUHV GLVFXVVHG LQ FKDSWHUV DQG DUH SUHVHQW ,Q &KDSWHU WKH LQYHUVH NLQHPDWLFV RI IRXU RUWKRJRQDO PDQLSXODWRUV DUH GHVFULEHG LQ PRUH GHWDLO PAGE 98 7DEOH ,QYHUVH NLQHPDWLFV RI RUWKRJRQDO PDQLSXODWRUV &ODVV 0HWKRG -XVWLILFDWLRQ $OO VL[ D[HV DUH SDUDOOHO )LYH FRQVHFXWLYH SDUDOOHO D[HV )RXU FRQVHFXWLYH SDUDOOHO D[HV )RXU FRQVHFXWLYH SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV )RXU FRQVHFXWLYH SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV &) f7KUHH SDLUV RI SDUDOOHO D[HV 7ZR SDLUV RI SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV ' PAGE 99 7DEOH f§&RQWLQXHG &ODVV 0HWKRG -XVWLILFDWLRQ )LYH FRQVHFXWLYH SDUDOOHO c D[HV )RXU FRQVHFXWLYH SDUDOOHO c D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV 7ZR SDLUV RI SDUDOOHO D[HV )RXU FRQVHFXWLYH SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV 7ZR SDLUV RI SDUDOOHO D[HV &) 7KUHH FRQVHFXWLYH SDUDOOHO D[HV 1RWDWLRQ 'HJHQHUDWH JHRPHWU\ &) &ORVHG)RUP 2QH 'LPHQVLRQDO LWHUDWLYH PHWKRG 7ZR'LPHQVLRQDO LWHUDWLYH PHWKRG PAGE 100 &+$37(5 $33/,&$7,21 (;$03/(6 ([DPSOH 7KH 380$ $ SRSXODU RUWKRJRQDO PDQLSXODWRU JHRPHWU\ WKH 380$ LV GHVFULEHG E\ WKH NLQHPDWLF SDUDPHWHUV JLYHQ LQ 7DEOH DQG LOOXVWUDWHG LQ )LJXUH 7KLV PDQLSXODWRU KDV D VSKHULFDO ZULVW DQG WKHUHIRUH DOORZV FORVHGIRUP VROXWLRQV 3LHSHU f ,QYHUVH NLQHPDWLF VROXWLRQV KDYH EHHQ SURSRVHG E\ QXPHURXV DXWKRUV IRU WKLV W\SH RI DUP /HH DQG =LHJOHU &UDLJ 3DXO DQG =KDQJ f 7DEOH 380$ NLQHPDWLF SDUDPHWHUV -RLQW G D D UGf ; 7 D G k D Q G k LW WW p 7KLV H[DPSOH LV LQFOXGHG KHUH WR GHPRQVWUDWH WKH XWLOLW\ RI WKH DSSURDFK DOUHDG\ RXWOLQHG DQG WR FRQWUDVW LW PAGE 101 , )LJXUH 7KH 380$ NLQHPDWLF VWUXFWXUH PAGE 102 ZLWK WKH JHRPHWULF DQG DOJHEUDLF DSSURDFKHV WDNHQ E\ WKH SUHYLRXV DXWKRUV :LWKRXW FRPSXWLQJ WKH IRUZDUG NLQHPDWLFV ZH ZLOO LOOXVWUDWH KRZ (TV ff PD\ EH HDVLO\ REWDLQHG )RU TXLFN UHIHUHQFH LQ WKH IROORZLQJ GLVFXVVLRQ ZH ZULWH WKH HTXDWLRQV LPPHGLDWHO\ W= a 6 & 6 & & f 3= D 6 D 6 G & f SW DD&f AA A AA f A A DAA f SaDAfDAfGAf§GAfDf G 6 D & f 7R LOOXVWUDWH WKH VLPSOLILFDWLRQ REWDLQHG E\ WKH IUDPH DVVLJQPHQW GHVFULEHG HDUOLHU DQG LQQHUSURGXFW LQYDULDQFH XQGHU URWDWLRQV ZH JLYH LQ GHWDLO WKH GHYHORSPHQW RI HTXDWLRQ f :LWK / O OJ DQG O G] (T f \LHOGV 3 A 5 A5A Af AA RU S 5A55 > 5 A 5 AA AA n %\ RUWKRJRQDOLW\ WKH LQQHUSURGXFW SS KDV WKH VDPH YDOXH DV WKH LQQHUSURGXFW RI WKH WHUP LQ EUDFNHWV KHQFH SS > 5B 55B @ r > 5OO 5Ua/@ PAGE 103 7KH LQQHUSURGXFW RI HDFK WHUP LQ WKH VTXDUH EUDFNHWV ZLWK LWVHOI LV WKH VTXDUH RI WKH OHQJWK RI WKDW YHFWRU )RU H[DPSOH 5 5 A r A AA A ArA DA AA AAr 7KHVH LQQHUSURGXFW PDQLSXODWLRQV UHSUHVHQW D FRQVLGHUDEOH DOJHEUDLF VLPSOLILFDWLRQ WKDW UHTXLUHV OLWWOH RU QR PHQWDO HIIRUW )XUWKHU WKH\ SURYLGH D PHWKRGRORJ\ DQG FRQVLGHUDEOH LQVLJKW LQWR KRZ WR ILQG RWKHU DOJHEUDLF UHGXFWLRQV 6RPH RI WKH FURVV WHUPV DOVR UHGXFH IRU LQVWDQFH 5 A f 5 A AA A r A AAn &RPSOHWH H[SDQVLRQ RI (T f DQG DSSOLFDWLRQ RI WKH UHGXFWLRQ WHFKQLTXHV MXVW GLVFXVVHG OHDG WR SA AAAf r>A AA 5 AA AA ArA AAr )RU WKLV PDQLSXODWRU YHFWRUV >G@7 G] f§ r7 5 >DG@ DQG 5/ >D! rn r@7 D [ DOORZ XV WR VLPSOLI\ WKH ODVW HTXDWLRQ WR SA f§A f§A f§Af G= >5 AA D 5 DA f [ HJ O5BO LV REYLRXVO\ ZKLFK HOLPLQDWHV k IURP WKLV HTXDWLRQf PAGE 104 :LWKRXW DQ\ PDWUL[ PXOWLSOLFDWLRQ UHTXLUHG ZH REWDLQ WKH IXOO\ VLPSOLILHG UHODWLRQ LQYROYLQJ k RQO\ 3DDGGf D G 6 D &f 7KH ODVW HTXDWLRQ \LHOGV DW PRVW WZR VROXWLRQV IRU k $IWHU DSSO\LQJ WULJRQRPHWULF LGHQWLWLHV IRU DQJOH VXPV WR f ZH JHW 3] D A D AaAa A a A AnAnf§ 6Af n DQG JURXSLQJ WHUPV ZH REWDLQ DD&G6f 6 D6G&f & S] :LWK HDFK YDOXH RI k YDOXHV IRU k FDQ EH REWDLQHG IURP WKLV ODVW HTXDWLRQ :LWK k DQG k NQRZQ f DQG f EHFRPH IXQFWLRQV RI k DQG k RQO\ $OWKRXJK WKLV V\VWHP RI HTXDWLRQV LQ WZR XQNQRZQV FDQ WKHRUHWLFDOO\ EH VROYHG LWV VROXWLRQ LV QRW REYLRXV $ VLPSOHU VROXWLRQ H[LVWV LI (TV f WR f DUH FRQVLGHUHG S [ 5A55 f f [ S[ f S \ 555 f f f \ 3\ f RU G 6 WfD & WfD & f A A A 3[ G &A G6D&D&f 6A S PAGE 105 7KH ODVW WZR (TV IRUP D OLQHDU V\VWHP LQ 6A DQG DQG SURYLGH D XQLTXH YDOXH IRU k (TV f DQG f DORQJ ZLWK f SURYLGH D ZD\ WR VROYH IRU DQG %\ VROYLQJ IRU & LQ f DQG VXEVWLWXWLQJ LQ W[ & & &6 6 A 66 & 6 & f W\ s & &6 & 66 6 6 &n f REWDLQ & &6 6O F 66 & W] & 6 f 6 &6 f & & 66 W\ & W] 6 6 r f 7KLV OLQHDU V\VWHP FDQ EH VROYHG IRU WKH SURGXFWV &6 DQG 66 XQLTXHO\ :KHQ 6 LV QRW WZR VROXWLRQV IRU k DUH WKHQ REWDLQHG E\ k $WDQ66A&6Af RU k $WDQa66A&6f :KHQ 6 MRLQW D[HV ] DQG ]A DUH DOLJQHG DQG WKH PDQLSXODWRU ORVHV RQH '2) 2QO\ WKH VXP kk FDQ EH IRXQG E\ XVH RI (TV f DQG f :LWK k NQRZQ WKH W[ DQG W\ HTXDWLRQV DERYH FRQVWLWXWH D OLQHDU V\VWHP RI HTXDWLRQV ZKLFK \LHOGV D XQLTXH VROXWLRQ IRU 7KH ODVW MRLQW YDULDEOH k FDQ WKHQ EH REWDLQHG IURP PRUH HTXDWLRQV IURP f VXFK DV WKH Q] DQG E] HTXDWLRQV PAGE 106 7KLV SURFHGXUH ZLOO \LHOG VROXWLRQV ZKLFK PXVW WKHQ EH FKHFNHG IRU MRLQW YDULDEOH UDQJH OLPLWDWLRQV :H HQG WKH GLVFXVVLRQ RI WKH 380$ H[DPSOH ZLWK WKH REVHUYDWLRQ WKDW WKH IRUZDUG NLQHPDWLFV ZHUH QHYHU GHWHUPLQHG WR REWDLQ WKH LQYHUVH NLQHPDWLF VROXWLRQ ([DPSOH 7KH *3 &RQVLGHU WKH PDQLSXODWRU JHRPHWU\ ZLWK NLQHPDWLF SDUDPHWHUV JLYHQ LQ 7DEOH 7KLV URERW DUP LV DQ H[LVWLQJ LQGXVWULDO PDQLSXODWRU WKDW EHORQJV WR WKH OL FODVV RI RUWKRJRQDO DUPV DQG GRHV QRW DOORZ FORVHGIRUP VROXWLRQV $OWKRXJK 7DEOH VSHFLILHV WKDW WKH PRVW FRPSOH[ DUP VWUXFWXUH ZLWKLQ WKH RUWKRJRQDO PDQLSXODWRUV FODVV FDQ EH VROYHG ZLWK D WZRGLPHQVLRQDO LWHUDWLYH WHFKQLTXH EXW WKH *3 )LJXUH f KDV WZR FRQVHFXWLYH SDLUV RI LQWHUVHFWLQJ D[HV DQG D SULVPDWLF MRLQW DQG LW FDQ EH VROYHG ZLWK D RQHGLPHQVLRQDO LWHUDWLYH WHFKQLTXH $QRWKHU UHDVRQ IRU GLVFXVVLQJ WKLV DUP KHUH LV WR VKRZ WKDW WKH WHFKQLTXHV GHYHORSHG LQ WKLV WH[W DSSO\ WR PDQLSXODWRUV ZLWK SULVPDWLF MRLQWV DV ZHOO $Q LWHUDWLYH PHWKRG WKDW H[DFWO\ FRPSXWHV WKH SRVLWLRQ EXW DSSUR[LPDWHV WKH RULHQWDWLRQ ZDV SURSRVHG IRU WKLV W\SH RI JHRPHWU\ E\ /XPHOVN\ f 7KH WHFKQLTXH SUHVHQWHG KHUH GLIIHUV LQ WKDW LW VROYHV IRU ERWK WKH RULHQWDWLRQ DQG WKH SRVLWLRQ ZLWK WKH VDPHn SUHFLVLRQ DQG LWLV DSSOLFDEOH WR D ODUJHU YDULHW\ RI PDQLSXODWRUV PAGE 107 )LJXUH 7KH *3 NLQHPDWLF VWUXFWXUH PAGE 108 7DEOH *3 PDQLSXODWRU NLQHPDWLF SDUDPHWHUV MRLQW G k D D 7 D 7 G 7 G 7 p -RLQW LV SULVPDWLF :H ZLOO LPSOHPHQW DQ LWHUDWLYH WHFKQLTXH WR ILQG WKH ]HURV RI D UHDO YDOXHG IXQFWLRQ RI A )LUVW ZH VKRZ WKDW NQRZOHGJH RI A LV VXIILFLHQW WR GHWHUPLQH D VROXWLRQ VHW $VVXPLQJ D JXHVV RI A WKH FRUUHVSRQGLQJ [ DQG ] FRPSRQHQWV RI S 5fS DQG FDQ EH FRPSXWHG 3; 3[ &L3\ VL f S] S[ 6M3\ &O f +[ W[ &MAW\ 6[ f OIF] 6OW\ &f f f f§ r )RU WKLV URERW A 5 D[ ‘rf A= G] DQG 5 :LWK WKHVH YDOXHV f \LHOGV S 5A5 A AA A A D A RU DIWHU PXOWLSOLFDWLRQ E\ 5A PAGE 109 S 5G 5] G = D [f f 9HFWRU W LV JLYHQ E\ W 5A W 555 ] f $ UHGXFHG V\VWHP RI HTXDWLRQV FDQ EH REWDLQHG IURP WKH ODVW r WZR HTXDWLRQV E\ FRQVLGHULQJ WKH H[SUHVVLRQV RI AS W W ] W S DQG -SS &RPSXWLQJ f§W] )URP (T f DQG XVLQJ (TV f DQG f DV QHFHVVDU\ \LHOGV W] W ] 5] 5B\ 6LQFH 5] >6 & @7 DQG 5B\ >6 &@7 WKH SUHFHGLQJ HTXDWLRQ EHFRPHV W] 6 6 f &RPSXWLQJ f§S] 6LQFH S] S ] IURP (T f SURSHUWLHV f DQG f DQG 5fA] \ ZH REWDLQ A‘3] G U] G ] D [f \ ZKLFK LV HDVLO\ VHHQ WR SURGXFH S] G & f &RPSXWLQJ f§Wf§S (TV f fDQG XVH RI (TV f DQG f \LHOG WS WS 5] G ] G 5B] D 5[f PAGE 110 :LWK 5] \ DQG 5]G] WKLV HTXDWLRQV UHGXFHV WR WS G &J D & 6A f &RPSXWLQJ SS 7KH LQQHU SURGXFW GLUHFWO\ SURGXFHV SS SS G G D D G 6 f ZLWKRXW DQ\ PDWUL[ RSHUDWLRQV (TXDWLRQ f FDQ EH XVHG WR GHILQH D UHDO IXQFWLRQ RI HOI LH I@f G & D & 6 WS f 9DOXHV RI k WKDW \LHOG D VROXWLRQ WR WKH ,QYHUVH NLQHPDWLFV RI WKLV PDQLSXODWRU PXVW EH ]HURV RI IXQFWLRQ I (TV f f DQG f SURYLGH D ZD\ WR FRPSXWH I JLYHQ k‘@B :LWK NQRZQ ;3[ AW[ DQG W] DUH IXOO\ GHWHUPLQHG (TXDWLRQ f WKHQ \LHOGV & f DQG 6 X 7ULJ&f f ZKHUH X RU H[SUHVVHV D VLJQ DPELJXLW\ DQG WKH IXQFWLRQ 7ULJ LV GHILQHG E\ 7ULJ[f O[f 7KH SULVPDWLF YDULDEOH G FDQ WKHQ EH IRXQG IURP (T f G SS D G D G 6f f PAGE 111 DQG IURP f WKH YDOXH RI FDQ EH FRPSXWHG LI V LV QRW ]HUR 6 W6nn f DQG & X 7ULJ6f f ZKHUH X RU LV DQRWKHU VLJQ DPELJXLW\ 7KLV DGGLWLRQDO VLJQ DPELJXLW\ FDQ EH DYRLGHG LI PRUH HTXDWLRQV LQYROYLQJ k DUH FRQVLGHUHG ,QGHHG (T f DOORZV XV WR GHULYH H[SUHVVLRQV IRU S[ DQG 3\ DV OS[ 5AG 5] G ] D [f [ DQG 3\ 5G U] G ] D ;f \ 7KHVH ODVW HTXDOLWLHV \LHOG D V\VWHP RI WZR HTXDWLRQV WKDW FDQ UHDGLO\ EH VROYHG IRU 6 DQG & 6 G 3; N 3]fGNRfn f & NR 3[ fG 3fGNfn f ZKHUH N4 D G 6f 7KH YDOXH RI & FDQ WKHQ EH REWDLQHG IURP HLWKHU WKH H[SUHVVLRQ IRU W\ AW\ 5 5 5 ] \ ZKLFK DIWHU XVLQJ SURSHUWLHV f DQG f JLYHV PAGE 112 & W]6 & 6f& f RU IURP f W-L 5 5 5 5 ] [ ZKLFK \LHOGV & & & 6 f f :LWK WKH FRPSXWHG YDOXHV RI G & & DQG 6 WKH YDOXH RI IWkf LV IXOO\ GHWHUPLQHG 7KH GHULYDWLYH RI I FDQ DOVR EH HYDOXDWHG %\ GLIIHUHQWLDWLQJ f ZLWK UHVSHFW WR A G&Gk FDQ EH REWDLQHG G&Gk 3[G f ZKHUH ZH VXEVWLWXWHG GS]fGk S[r 7KH YDOXH RI G6Gk FDQ EH REWDLQHG E\ GLIIHUHQWLDWLQJ WKH 3\WKDJRUHDQ LGHQWLW\ G>6 &@Gk GOfGk DQG VROYLQJ IRU G6Gk G6Gk[ & G&Gkf6 & 3;6 Gf f 'LIIHUHQWLDWLQJ f \LHOGV GGfGk D G G6GkfG 6XEVWLWXWLQJ IURP (T f JLYHV GGGk aD A A A3[p GA Gf f PAGE 113 DQG IURP f G6JGkA FDQ EH REWDLQHG G6Gk 6 G6Gkf@6 f 2QFH DJDLQ IURP GLIIHUHQWLDWLRQ RI WKH 3\WKDJRUHDQ LGHQWLW\ G&Gk 6 G6Gkf& f DQG GIGkA LV ILQDOO\ REWDLQHG E\ GLIIHUHQWLDWLQJ HTXDWLRQ f GIGH/ D >& G6Gkf 6 G&AGkA @ >G G&Gkf & GGGkfM f %\ XVH RI WKH RQHGLPHQVLRQDO 1HZWRQ5DSKVRQ LWHUDWLYH PHWKRG D QHZ HVWLPDWH IRU kAA LV JLYHQ E\ nQHZ HL IkLf GIGkf 2QFH A LV REWDLQHG WR WKH GHVLUHG DFFXUDF\ WKH UHPDLQLQJ MRLQW YDULDEOHV k k DQG k DUH WKHQ FRPSXWHG IURP WKH YDOXHV RI WKHLU VLQHV DQG FRVLQHV DV REWDLQHG DORQJ ZLWK G IURP WKH ODVW LWHUDWLRQ $ YHFWRU HTXDWLRQ LQ k FDQ EH REWDLQHG IURP f ZKLFK JLYHV 5 5B 5 5O 5 [ f 7KLV HTXDWLRQ FDQ EH VROYHG XQLTXHO\ IRU k PAGE 114 ,Q SUDFWLFDO VLWXDWLRQV WKH GHULYDWLYH RI I FDQ EH HVWLPDWHG E\ GIGH/ > I MA 6kBf Ikf @ kA ZKHUH kA LV D VPDOO LQFUHPHQW RI kA :KHQ WKH YDOXH RI kA LV FORVH HQRXJK WR D VROXWLRQ WKH FRPSOH[LW\ FDQ EH UHGXFHG E\ FRPSXWLQJ GIGkA QXPHULFDOO\ DW DQ\ LWHUDWLRQ XVLQJ WKH YDOXHV RI kA DQG Ikf LQ WKH SUHFHGLQJ LWHUDWLRQ GIGkA ILB ILf4La kLf ZKHUH WKH VXSHUVFULSW UHSUHVHQWV WKH LWHUDWLRQ QXPEHU DW ZKLFK WKH YDULDEOH LV FRPSXWHG 7KLV VDYHV WKH FRPSXWDWLRQDO FRVW RI (TV f WKURXJK f DQG DYRLGV WKH SUREOHP RI VSHFLDO FDVHV WKDW RFFXU ZKHQ GLYLVLRQ E\ D QXPEHU FORVH WR ]HUR LV QHHGHG LQ DQ\ RI WKRVH HTXDWLRQV 7KH SURFHGXUH MXVW GHVFULEHG ZDV SURJUDPPHG WR FRPSXWH WKH MRLQW YDULDEOHV IRU HTXLGLVWDQW SRLQWV RQ D OLQHDU WUDMHFWRU\ ZLWK FRQVWDQW RULHQWDWLRQ WKDW ZLOO PRYH WKH HQG HIIHFWRU IURP WKH LQLWLDO SRVH 3 PAGE 115 WR WKH SRVLWLRQ > @7 7DEOH VKRZV WKH RXWSXW RI WKH SURJUDP 7DEOH *3 WUDMHFWRU\ SRLQWV LQ MRLQW FRRUGLQDWHVf HO p G k LQ k f $OO DQJOHV DUH LQ GHJUHHV k Ff§L n R ,, LQ 77KH PD[LPXP QXPEHU RI LWHUDWLRQV QHHGHG SHU SRLQW ZDV VL[ 7KH JXHVV IRU HDFK SRLQW ZDV WKH YDOXH RI k DW WKH SUHFHGLQJ SRLQW 7KH H[SHULPHQW ZDV VWDUWHG ZLWK D JXHVV RI r &RQYHUJHQFH DW HYHU\ SRLQW ZDV REWDLQHG ZKHQ RU PRUH SRLQWV ZHUH WDNHQ DORQJ WKH WUDMHFWRU\ $OWKRXJK 7DEOH JLYHV WKH MRLQW YDULDEOHV WR RQO\ GHFLPDO SODFHV WKH\ ZHUH FRPSXWHG ZLWK D SUHFLVLRQ RI 7KH SURJUDP ZDV ZULWWHQ LQ & DQG UXQ RQ DQ $7t7 % GHVNWRS FRPSXWHU PAGE 116 7KH NLQHPDWLF LQYHUVLRQ IRU WKH SRLQWV WRRN VHFRQGV ZKLFK JLYHVDQDYHUDJH WLPH SHU NLQHPDWLF LQYHUVLRQ RI PLOOLVHFRQGV FOHDUO\ VXLWDEOH IRU UHDOWLPH KLJK SUHFLVLRQ LQYHUVH NLQHPDWLFV ([DPSOH 7KH 20 0DQLSXODWRU ,Q WKLV H[DPSOH ZH SUHVHQW DQ RUWKRJRQDO PDQLSXODWRU WKDW FDQ DFKLHYH D JLYHQ HQGHIIHFWRU SRVH LQ VL[WHHQ GLVWLQFW FRQILJXUDWLRQV %HVLGHV WKLV LQWHUHVWLQJ SRLQW ZH GLVFXVV WKLV PDQLSXODWRU WR VKRZ WKH SRZHU RI WKH VLPSOH LWHUDWLYH WHFKQLTXHV GHYHORSHG LQ WKLV GLVVHUWDWLRQ QRW RQO\ DV IDVW LQYHUVH NLQHPDWLF PHWKRGV EXW DOVR DV LQWHUDFWLYH LQYHUVH NLQHPDWLF DQDO\VLV WRROV FDSDEOH RI ILQGLQJ DOO WKH VROXWLRQV IRU FHUWDLQ PDQLSXODWRUV 7KH 20 PDQLSXODWRU LV LOOXVWUDWHG LQ )LJXUH DQG LWV '+SDUDPHWHUV DUH OLVWHG LQ 7DEOH 7DEOH '+SDUDPHWHUV RI 20 PDQLSXODWRU -RLQW G D D R H k DA/ 7 D 7 D 7 PAGE 117 ORJ PAGE 118 7KLV URERW FRPELQHV WKH IROORZLQJ VSHFLDO VWUXFWXUHV LGHQWLILHG LQ &KDSWHU &DVH LV VDWLVILHG E\ WKH IRXU'2) VHJPHQW ]WR ] &DVH LV VDWLVILHG E\ WKH VHJPHQW ]4 WR ] DQG E\ WKH VHJPHQW ] WR ] &DVH LV VDWLVILHG E\ WKH VHJPHQW WR ] &DVH LV VDWLVILHG E\ WKH VHJPHQW ] WR ] 7KH VWUXFWXUH RI WKLV DUP DOWKRXJK VLPSOH HQRXJK WR DOORZ WKH XVH RI D RQHGLPHQVLRQDO LWHUDWLYH WHFKQLTXH DV VHHQ LQ &KDSWHU f VWLOO GRHV QRW DOORZ FORVHG IRUP VROXWLRQV 2QFH DJDLQ ZH ZLOO LPSOHPHQW DQ LWHUDWLYH WHFKQLTXH EDVHG RQ ILQGLQJ WKH ]HURV RI D UHDO YDOXHG IXQFWLRQ RI A :LWK O NQRZQ LQLWLDO HVWLPDWHf WKH YHFWRUV W ] f DQG &O3; 6O3\ ;S 5S S] VL3[ FO3\ f DUH IXOO\ GHWHUPLQHG ([SUHVVLRQV IRU W] 3= WS DQG fASAS SS DUH JLYHQ LQ WHUPV RI WKH UHPDLQLQJ MRLQW DQJOHV E\ f PAGE 119 ,OO D 6 G f D 6 6 D & DO &f f W S f D & D A DL Af G D 6 DO D & >SS D[ D D G@ f ([SUHVVLRQV IRU W[ AW\ ASA DQG AS\ SURYLGH WKH DGGLWLRQDO HTXDWLRQV f f f f ,I WKH IXQFWLRQ I LV GHILQHG IURP HTXDWLRQ f WKHQ IRU D JLYHQ YDOXH RI kf@B WKH FRUUHVSRQGLQJ YDOXHV RI 6 6 & DQG & PXVW EH FRPSXWHG EHIRUH IkOf D 6 6 D & D &f WS f FDQ EH HYDOXDWHG &RPSXWLQJI *LYHQ MB WKH FRPSRQHQWV RI W DQG S DUH FRPSXWHG IURP (TV f DQG f 7KH YDOXH RI & DQG 6 DUH WKHQ JLYHQ E\ (T f F DQG 6 a X 7ULJ&f PAGE 120 ZKHUH X LV D VLJQ DPELJXLW\ DQG 7ULJ[f [f (TXDWLRQ f DQG f \LHOG & V W[6 f 6 W] 6 f UHVSHFWLYHO\ ZKHQ 6 LV QRW ]HUR ,Q WKH VSHFLDO FDVH ZKHUH 6 KDV DQ H[WUHPHO\ VPDOO DEVROXWH YDOXH k RU U DQG WKH FXUUHQW YDOXH RI k ZLOO DOORZ FORVHG IRUP VROYLQJ RI WKH UHPDLQLQJ MRLQW YDULDEOHV DQG ILkAf FDQ VWLOO EH FRPSXWHG 1H[W 6 DQG & DUH FRPSXWHG IURP HTXDWLRQ f &2 ,, ;3= a GfD f ,, X X 7ULJ6f f ZKHUH X LV DQRWKHU VLJQ DPELJXLW\ DQG & DQG 6 DUH REWDLQHG IURP f DQG f UHVSHFWLYHO\ F ;S[ D & & DLfD f 6 3] f D F VADr f )LQDOO\ WKH YDOXHV RI k DQG k DUH FRPSXWHG DV k DWDQ6&f DWDQ6&f DQG LL LQ &' DADQ 6&f DWDQ 6&f PAGE 121 DQG IWkA FDQ EH FRPSXWHG $ IHZ SRLQWV DUH QRWHZRUWK\ LQ WKLV GHULYDWLRQ )LUVW VLQFH WKH DERYH SURFHGXUH FRPSXWHV I IURP D JXHVV kA DQG QRW D YDOXH RI A WKDW FRUUHVSRQGV WR D WUXH VROXWLRQ VHW WKH YDOXHV RI VLQH DQG FRVLQH RI DQ\ DQJOH FRPSXWHG IURP GLIIHUHQW HTXDWLRQV VXFK DV f DQG f IRU k RU f DQG f IRU kf ZLOO LQ JHQHUDO QRW VDWLVI\ WKH 3\WKDJRUHDQ LGHQWLW\ f $Q DOWHUQDWH SRVVLELOLW\ LV WR XVH RQH RI WKH WZR HTXDWLRQV WR VROYH IRU RQH WULJRQRPHWULF IXQFWLRQ HLWKHU VLQH RU FRVLQH FRPSXWH WKH RWKHU IURP HTXDWLRQ f DQG XVH WKH VHFRQG HTXDWLRQ WR DYRLG D VLJQ DPELJXLW\ RQO\ )RU H[DPSOH LQVWHDG RI XVLQJ (T f ZH FDQ FRPSXWH 6 IURP 6 VLQW]Vf 7UL"Ff f WR LQVXUH FRPSDWLELOLW\ ZLWK LGHQWLW\ f $V GLVFXVVHG LQ &KDSWHUV DQG WKH DELOLW\ WR FRPSXWH WKH IXQFWLRQ I4Af SURYHG VXIILFLHQW WR SURYLGH D SUDFWLFDO RQHGLPHQVLRQDO LQYHUVH NLQHPDWLF DOJRULWKP IRU WKH PDQLSXODWRU RI )LJXUH 7KH VLJQ DPELJXLWLHV X DQG X DERYH JLYH IRXU SRVVLEOH FRPELQDWLRQV WKDW PXVW DOO EH WULHG LQ WKH VHDUFK IRU D URRW RI WKH IXQFWLRQ I 2QFH D URRW RI I LV IRXQG WKH YDOXHV RI kA k DQG k DUH NQRZQ DORQJ ZLWK D YDOXH IRU & IURP WKH ODVW LWHUDWLRQ PAGE 122 $ RQHGLPHQVLRQDO 1HZWRQ5DSKVRQ DOJRULWKP ZDV SURJUDPPHG WR ILQGn WKH ]HURV RI WKH IXQFWLRQ I GHILQHG LQ (T f ZLWK G D D D 2QFH D YDOXH RI kA IRU ZKLFK Ikf ZDV IRXQG WKH FRUUHVSRQGLQJ VROXWLRQ VHW ZDV FRPSOHWHG DQG FKHFNHG IRU FRQVLVWHQF\ E\ YHULI\LQJ WKDW WKH VROXWLRQ VHW VDWLVILHV WKH H[SUHVVLRQ IRU W\ DV REWDLQHG IURP (T f 7KLV VLPSOH WHVW SURYHG HIIHFWLYH LQ ILOWHULQJ RXW H[WUDQHRXV VROXWLRQV IRU WKLV SDUWLFXODU H[SHULPHQW $ PRUH LQYROYHG FRQVLVWHQF\ YHULILFDWLRQ SURFHGXUH PD\ EH UHTXLUHG IRU GLIIHUHQW PDQLSXODWRUV +RZHYHU &RPSXWLQJ WKH FRPSOHWH IRUZDUG NLQHPDWLFV IURP (T f DQG YHULI\LQJ DOO SRVH HOHPHQWV FRQVWLWXWHV D ZRUVW FDVH FRQGLWLRQ ,QYHUVH .LQHPDWLF 6ROXWLRQ 6HDUFK $OJRULWKP 7KH RQHGLPHQVLRQDO LQYHUVH NLQHPDWLF PHWKRG MXVW GHVFULEHG ZDV SURJUDPPHG LQ SDVFDO RQ D SHUVRQDO PLFURFRPSXWHU $ VLPSOH VHDUFK DOJRULWKP ZDV WKHQ LPSOHPHQWHG E\ VHOHFWLQJ UHJXODUO\ VSDFHG YDOXHV RI WKH LQLWLDO HVWLPDWH RI A ZLWKLQ WKH LQWHUYDO > Uf ZLWK WKH SUREOHP SRVH PAGE 123 7KLV VHDUFK SURJUDP ZDV UXQ IRU HDFK RI WKH IRXU SRVVLEOH FRPELQDWLRQV RI YDOXHV IRU WKH VLJQ DPELJXLWLHV X DQG X f f f DQG ff 7KH VROXWLRQ VHWV IRXQG DUH OLVWHG LQ 7DEOH 7KLV UHVXOW LV RI LPSRUWDQFH EHFDXVH LW SURYLGHV WKH ILUVW WDQJLEOH SURRI WKDW D VL['2) PDQLSXODWRU FDQ DFWXDOO\ DFKLHYH D JLYHQ SRVH ZLWK GLIIHUHQW FRQILJXUDWLRQV 6RPH PDQLSXODWRUV FDQ DFKLHYH D SDUWLFXODU HQGHIIHFWRU SRVH LQ DQ LQILQLWH QXPEHU RI FRQILJXUDWLRQV ZKHQ WZR RU PRUH MRLQW D[HV FRLQFLGH 6XFK GHJHQHUDWH FRQGLWLRQV ZKHUH WKH PDQLSXODWRU ORVHV GHJUHHV RI IUHHGRP IRUFH WKH PDQLSXODWRU MDFRELDQ WR EHFRPH VLQJXODU 7R YHULI\ WKDW WKH PDQLSXODWRU XQGHU GLVFXVVLRQ LV QRQGHJHQHUDWH DW HDFK RI WKH VL[WHHQ FRQILJXUDWLRQV IRXQG ZH FRPSXWH WKH GHWHUPLQDQW RI WKH PDQLSXODWRU -DFRELDQ 7KH V\PEROLF -DFRELDQ RI D '2) PDQLSXODWRU KDV LWV VLPSOHVW H[SUHVVLRQ LQ IUDPH PLGIUDPHf 5HQDXG Df )RU WKH URERW GHVFULEHG KHUH WKH PLGIUDPH -DFRELDQ FRPSXWHG XVLQJ WDEOHV JLYHQ LQ 'RW\ f LV & 6 6 af& & 6 & & 6 6 LQ D & PAGE 124 7DEOH 0 PDQLSXODWRU FRQILJXUDWLRQV IRU SRVH 3 RI HTXDWLRQ f k HO k k k G PAGE 125 7KH GHWHUPLQDQW RI WKH PDQLSXODWRU -DFRELDQ GM LV LQGHSHQGHQW RI WKH IUDPH RI H[SUHVVLRQ DQG FDQ EH HDVLO\ REWDLQHG IURP PDWUL[ G& 6 W6 r &A f rn & &6 6 & & 6f` f 7KH YDOXHV RI GM OLVWHG LQ 7DEOH SURYH WKDW DOO VL[WHHQ VROXWLRQV IRXQG FRUUHVSRQG WR QRQGHJHQHUDWH FRQILJXUDWLRQV RI WKH 0 URERW DUP )LJXUH VKRZV SKRWRJUDSKV RI D FRPSXWHU JUDSKLFV VLPXODWLRQ RI WKH 20 PDQLSXODWRU LQ WKH VL[WHHQ FRQILJXUDWLRQV OLVWHG LQ 7DEOH )LJXUH LV D KDQG GUDZLQJ RI WKLV PDQLSXODWRU LQ FRQILJXUDWLRQ RI 7DEOH LH FRUUHVSRQGLQJ WR WKH ILUVW VROXWLRQ VHWf ZLWK DOO OLQN IUDPHV FOHDUO\ LQGLFDWHG DQG WR KHOS GLIIHUHQWLDWH EHWZHHQ VROXWLRQV ZLWK FRPPRQ YDOXHV RI O DQG k ZH KDYH DWWHPSWHG WR LQGLFDWH WKH GLUHFWLRQ RI D[LV YHFWRUV ] ] ] DQG ] RQ WKH SKRWRJUDSKV 7KH SRVLWLRQ DQG RULHQWDWLRQ RI WKH HQGHIIHFWRU DQG WKH EDVH IUDPH DV VKRZQ RQ )LJ f DUH WKH VDPH IRU DOO VL[WHHQ UHSUHVHQWDWLRQV RI )LJXUH ,W LV DOVR LQWHUHVWLQJ WR QRWH WKDW WKLV ODUJH QXPEHU RI VROXWLRQV FDQ EH UHDOL]HG E\ DQ RUWKRJRQDO PDQLSXODWRU ZLWK D IDLUO\ VLPSOH JHRPHWU\ )LQDOO\ WKLV H[DPSOH VKRZV WKDW WKH WHFKQLTXHV GHYHORSHG LQ WKLV GLVVHUWDWLRQ FDQ EH XVHG WR LPSOHPHQW VLPSOH DQG HIILFLHQW LQYHUVH NLQHPDWLF DQDO\VLV WRROV VXFK DV WKH VHDUFK DOJRULWKP MXVW GLVFXVVHG PAGE 126 f f )LJXUH &RPSXWHU VLPXODWLRQ RI WKH VL[WHHQ FRQILJXUDWLRQV RI 7DEOH PAGE 127 f f f f )LJXUH f§&RQWLQXHG PAGE 128 f f f )LJXUH f§&RQWLQXHG PAGE 129 f f )LJXUH f§&RQWLQXHG PAGE 130 ZKLFK KDV IRXQG DOO WKH VROXWLRQV WR WKH LQYHUVH NLQHPDWLFV SUREOHP RI WKH 20 PDQLSXODWRU ([DPSOH 20 0DQLSXODWRU 7KH PRVW NLQHPDWLFDOO\ FRPSOH[ RUWKRJRQDO PDQLSXODWRU FODVV LV WKH RFWDO f FODVV GHVFULEHG E\ WKH '+ SDUDPHWHUV RI 7DEOH LQ ZKLFK QR WZR FRQVHFXWLYH MRLQW D[HV DUH SDUDOOHO ,Q WKLV H[DPSOH ZH ZLOO FRQVLGHU D PDQLSXODWRU ZLWK WKH DUELWUDULO\ FKRVHQ NLQHPDWLF SDUDPHWHUV G G GA GA DA D D D D VR WKDW WKHUH DUH QR WZR FRQVHFXWLYH D[HV LQWHUVHFWLQJ HLWKHU 7KH JHQHUDO WZRGLPHQVLRQDO 1HZWRQ5DSKVRQ PHWKRG GHVFULEHG LQ &KDSWHU IRU D JHQHUDO VL['2) PDQLSXODWRU ZDV SURJUDPPHG RQ D SHUVRQDO PLFURFRPSXWHU DQG UXQ ZLWK WKH PDQLSXODWRU MXVW GHVFULEHG DQG WKH &DUWHVLDQ HQGHIIHFWRU SRVH 3 f PAGE 131 7DEOH '+SDUDPHWHUV RI 20 0DQLSXODWRU -RLQW GL kL DL DLUGf k DO 7 G k D 77 G k D ,7 G k D ,7 G k D WW k 7KH VROXWLRQ VHW k k k k k kf r r r r r rf ZDV IRXQG LQ LWHUDWLRQV ZLWK DQ LQLWLDO HVWLPDWH RI f IRU A kf DQG DQ DFFXUDF\ RI 7KH VDPH VROXWLRQ VHW ZDV REWDLQHG LQ LWHUDWLRQV IURP DQ LQLWLDO HVWLPDWH RI r rf ZLWK WKH VDPH SUHFLVLRQ $ VHFRQG VROXWLRQ VHW JLYHQ E\ r r r r r rf ZDV IRXQG ZLWK WKH LQLWLDO HVWLPDWH r rf LQ LWHUDWLRQV ZLWK WKH VDPH DFFXUDF\ PAGE 132 ([DPSOH $ *HQHUDO *HRPHWU\ '2) 0DQLSXODWRU 7KH SUHYLRXV H[DPSOHV ZHUH DOO DERXW RUWKRJRQDO PDQLSXODWRUV +HUH ZH H[DPLQH D QRQRUWKRJRQDO PDQLSXODWRU ZLWK QR VSHFLDO VWUXFWXUH DV GHVFULEHG E\ WKH NLQHPDWLF SDUDPHWHUV RI 7DEOH DQG WKH &DUWHVLDQ HQGHIIHFWRU SRVH 3 f 7DEOH '+SDUDPHWHUV RI D QRQRUWKRJRQDO PDQLSXODWRU -RLQW G D D p r &0 f 2 R LQ &' R R r r p r 7KH WZRGLPHQVLRQDO 1HZWRQ5DSKVRQ PHWKRG RI &KDSWHU ZDV SURJUDPPHG WR ILQG D VROXWLRQ VHW :LWK WKH LQLWLDO HVWLPDWH f rf WKH VROXWLRQ VHW r r r r r rf PAGE 133 ZDV IRXQG LQ LWHUDWLRQV ZLWK DQ DFFXUDF\ RI fA 7KLV UHVXOW LV W\SLFDO RI WKH HIILFLHQF\ RI WKH WZRGLPHQVLRQDO 1HZWRQ5DSKVRQ LQYHUVH NLQHPDWLFV WHFKQLTXH PAGE 134 &+$37(5 &21&/86,21 $1' )8785( :25. 7KLV UHVHDUFK KDV DGGUHVVHG WKH LQYHUVH NLQHPDWLFV SUREOHP RI QRQUHGXQGDQW DOOUHYROXWH URERW PDQLSXODWRUV :H ILUVW VKRZHG KRZ D FRQYHQLHQW FKRLFH RI PDQLSXODWRU IUDPHV DQG SURSHU XVH RI LQQHUSURGXFW LQYDULDQFH RI URWDWLRQ WUDQVIRUPDWLRQV FDQ EH XVHG WR HDVLO\ UHGXFH WKH LQYHUVH NLQHPDWLF SUREOHP WR IRXU VLPSOH HTXDWLRQV LQGHSHQGHQW RI WZR RI WKH MRLQW YDULDEOHV 'RW\ f )RU IRXUD[LV URERWV WKH UHGXFHG V\VWHP RI HTXDWLRQV FDQ DOZD\V EH VROYHG LQ FORVHGIRUP DQG DW PRVW WZR LQYHUVH NLQHPDWLF VROXWLRQ VHWV FDQ EH IRXQG :H KDYH GHWHUPLQHG WKDW LQ JHQHUDO D '2) DUP ZLOO \LHOG D XQLTXH VROXWLRQ DQG ZH LGHQWLILHG WHQ VSHFLDO IRXU'2) VWUXFWXUHV IRU ZKLFK WZR VROXWLRQV FDQ EH IRXQG 7KH VDPH WHQ '2) VSHFLDO VWUXFWXUHV ZKHQ SDUW RI D ILYHD[LV URERW PDQLSXODWRU DUH VXIILFLHQW WR LQVXUH FORVHG IRUP VROXWLRQV IRU WKH '2) VWUXFWXUH 2WKHUZLVH ZH KDYH VKRZQ WKDW WKH LQYHUVH NLQHPDWLF SUREOHP UHGXFHV WR ILQGLQJ WKH ]HURV RI D UHDOYDOXHG IXQFWLRQ RI RQH MRLQW YDULDEOH 7KH PRVW NLQHPDWLFDOO\ FRPSOH[ '2) DUP FDQ WKHUHIRUH EH VROYHG E\ D IDVW RQHGLPHQVLRQDO LWHUDWLYH WHFKQLTXH VXFK DV WKH UHJXODU 1HZWRQ5DSKVRQ RU VHFDQW PHWKRG PAGE 135 ,Q WKH DQDO\VLV RI VL[GHJUHHRIIUHHGRP PDQLSXODWRUV ZH LGHQWLILHG WKUHH PDMRU FODVVHV RI '2) DUPV DFFRUGLQJ WR WKHLU NLQHPDWLF FRPSOH[LW\ )LUVW WKH FODVV RI FORVHGIRUP DUPV LQ ZKLFK ZH ILQG DOO '2) RSHQ NLQHPDWLF FKDLQV ZLWK WKUHH DGMDFHQW MRLQW D[HV LQWHUVHFWLQJ DW D FRPPRQ SRLQW 3LHSHU f RU ZLWK WKUHH SDUDOOHO DGMDFHQW MRLQW D[HV :H GLVFRYHUHG WKDW WKH '2) DUPV ZLWK WKUHH SDLUV RI WZR SDUDOOHO D[HV DQG WKRVH ZLWK WZR LQWHUVHFWLQJ D[HV IROORZLQJ RU SUHFHGLQJ WZR SDLUV RI SDUDOOHO MRLQW D[HV KDG FORVHG IRUP VROXWLRQV DV ZHOO 7KH QH[W FODVV FRQWDLQV DOO '2) PDQLSXODWRUV WKDW GR QRW DOORZ FORVHGIRUP VROXWLRQV EXW DUH VXFK WKDW NQRZOHGJH RI RQH MRLQW YDULDEOH LV VXIILFLHQW WR REWDLQ D FRPSOHWH VROXWLRQ VHW LQ FORVHGIRUP :H GHWHUPLQHG WKDW DOO '2) DUPV WKDW LQFOXGH RQH RI WKH WHQ VSHFLDO '2) VWUXFWXUHV GLVFXVVHG HDUOLHU ZHUH LQ WKLV VHFRQG FODVV 7KH LQYHUVH NLQHPDWLFV SUREOHP IRU WKHVH PDQLSXODWRUV UHGXFHV WR ILQGLQJ WKH ]HURV RI D UHDO YDOXHGIXQFWLRQ $ RQHGLPHQVLRQDO 1HZWRQ5DSKVRQ RU RWKHU LWHUDWLYH PHWKRG FDQ EH XVHG WR VROYH WKH LQYHUVH NLQHPDWLFV SUREOHP IRU WKHVH URERWV 7KH WKLUG FODVV RI VL[GHJUHHRIIUHHGRP URERWV FRQWDLQV DOO WKH PDQLSXODWRUV WKDW GR QRW IDOO LQWR WKH WZR SUHFHGLQJ FODVVHV )RU WKH PRVW NLQHPDWLFDOO\ FRPSOH[ VL[ '2) URERW PDQLSXODWRUV WKH LQYHUVH NLQHPDWLFV SUREOHP UHGXFHV WR VROYLQJ D QRQOLQHDU V\VWHP RI RQO\ WZR HTXDWLRQV LQ RQO\ WZR RI WKH MRLQW YDULDEOHV 7KHUHIRUH WKH URERWV PAGE 136 LQ WKLV WKLUG FODVV FDQ VWLOO EH VROYHG XVLQJ D IDVW WZR GLPHQVLRQDO LWHUDWLYH WHFKQLTXH 7KLV WZRGLPHQVLRQDO PHWKRG VWLOO FRQVWLWXWHV D ODUJH UHGXFWLRQ LQ FRPSXWDWLRQDO FRPSOH[LW\ ZLWK UHVSHFW WR WKH XVXDO VL[GLPHQVLRQDO LWHUDWLYH WHFKQLTXHV IRXQG LQ WKH OLWHUDWXUH 7KH GLYLVLRQ RI WKH VHW RI DOO '2) PDQLSXODWRUV LQWR WKH WKUHH FODVVHV MXVW GLVFXVVHG LV LOOXVWUDWHG LQ )LJXUH ,Q &KDSWHU ZH SURYLGH D IRUPDO GHILQLWLRQ RI RUWKRJRQDO PDQLSXODWRUV 'RW\ f 7KLV W\SH RI PDQLSXODWRU LV LPSRUWDQW VLQFH LW LQFOXGHV DOPRVW DOO H[LVWLQJ LQGXVWULDO URERW PDQLSXODWRUV :H VKRZ WKDW D VWUXFWXUDO SDUWLWLRQ RI DOO RUWKRJRQDO PDQLSXODWRUV LQWR WZHQW\ IRXU FODVVHV LV SRVVLEOH EXW RUWKRJRQDO PDQLSXODWRUV FDQ DOVR EH FODVVLILHG LQ WHUPV RI NLQHPDWLF FRPSOH[LW\ 2XW RI WKH WZHQW\ IRXU SDUWLWLRQV IRXQG WZHOYH FDQ DOZD\V EH VROYHG LQ FORVHG IRUP WKUHH FODVVHV DUH VXFK WKDW WKHLU PRVW NLQHPDWLFDOO\ FRPSOH[ HOHPHQWV FDQ EH VROYHG ZLWK D RQHGLPHQVLRQDO LWHUDWLYH PHWKRG DQG WKH UHPDLQLQJ QLQH FODVVHV RI RUWKRJRQDO PDQLSXODWRUV KDYH HOHPHQWV IRU ZKLFK D WZRGLPHQVLRQDO LWHUDWLYH WHFKQLTXH PD\ EH UHTXLUHG ,Q &KDSWHU ZH DQDO\]H WKH LQYHUVH NLQHPDWLFV RI ILYH PDQLSXODWRUV 7KH 380$ LQYHUVH NLQHPDWLFV LV GLVFXVVHG WR LOOXVWUDWH WKH XWLOLW\ RI WKH QHZ LQYHUVH NLQHPDWLF DSSURDFK HYHQ IRU DUPV WKDW DOORZ FORVHGIRUP VROXWLRQV 7KH *3 DQRWKHU H[LVWLQJ LQGXVWULDO URERW WKDW GRHV QRW DOORZ FORVHG IRUP VROXWLRQV LV DQDO\]HG IRU WZR PDMRU PAGE 137 '2) PDQLSXODWRUV VROYDEOH LQ FORVHGIRUP '2) PDQLSXODWRUV IRU ZKLFK WKH RQHGLPHQVLRQDO PHWKRG LV DSSOLFDEOH 6HW RI DOO '2) 0DQLSXODWRUV 6ROYDEOH E\ XVH RI D WZRGLPHQVLRQDO LWHUDWLYH PHWKRG )LJXUH O 6XEGLYLVLRQ RI '2) PDQLSXODWRUV LQ WHUPV RI LQYHUVH NLQHPDWLF WHFKQLTXHV PAGE 138 UHDVRQV )LUVW WR VKRZ WKDW WKH RQHGLPHQVLRQDO 1HZWRQ 5DSKVRQ DOJRULWKP FDQ SHUIRUP NLQHPDWLF LQYHUVLRQV LQ UHDOn WLPH PLOOLVHFRQGV SHU NLQHPDWLF LQYHUVLRQ RQ DQ $7t7 % GHVNWRS FRPSXWHU WKLV ILJXUH GURSV WR PLOOLVHFRQGV RQ DQ $7t7 % FRPSXWHUf 7KH VHFRQG UHDVRQ LV WKH SUHVHQFH RI D SULVPDWLF MRLQW $OWKRXJK WKLV GLVVHUWDWLRQ ZDV RQO\ FRQFHUQHG ZLWK DOOUHYROXWH PDQLSXODWRUV WKH *3 URERW H[DPSOH VKRZV WKDW WKH WHFKQLTXHV GHYHORSHG KHUHLQ DUH DSSOLFDEOH WR PDQLSXODWRUV ZLWK SULVPDWLF MRLQWV DV ZHOO ,Q H[DPSOH ZH GLVFXVVHG DQ RUWKRJRQDO PDQLSXODWRU RI VLPSOH JHRPHWU\ \HW QRW VLPSOH HQRXJK WR DOORZ FORVHGIRUP VROXWLRQV 7KH 20 URERW LOOXVWUDWHV WKH XVH RI WKH RQHn GLPHQVLRQDO WHFKQLTXH DV DQ RIIOLQH DQDO\VLV WRRO %\ LQWHUDFWLYHO\ YDU\LQJ WKH URERW SDUDPHWHUV DQG WKH HQG HIIHFWRU SRVH SDUDPHWHUV LQ VHDUFK RI D PD[LPXP QXPEHU RI LQYHUVH NLQHPDWLF VROXWLRQV WKH PDQLSXODWRU DQG WKH HQG HIIHFWRU SRVH RI &KDSWHU H[DPSOH ZHUH GLVFRYHUHG ,I WKH ZRUN RI /HH DQG /LDQJ LQ SUHVVf SXWV DQ XSSHU ERXQG RI VL[WHHQ RQ WKH QXPEHU RI SRVVLEOH LQYHUVH NLQHPDWLF VROXWLRQV RI VL['2) URERWV WKH 20 PDQLSXODWRU ZLWK WKH VL[WHHQ VROXWLRQV IRXQG HVWDEOLVKHV DV WKH OHDVW XSSHU ERXQG RQ WKH QXPEHU RI VROXWLRQV WR WKH LQYHUVH NLQHPDWLFV SUREOHP 7KH LWHUDWLYH WHFKQLTXHV GHVFULEHG LQ WKLV GLVVHUWDWLRQ KDYH VHYHUDO DGYDQWDJHV RYHU RWKHU H[LVWLQJ QXPHULFDO PAGE 139 WHFKQLTXHV 7KH\ GR QRW UHTXLUH WKH FRPSXWDWLRQ RI WKH PDQLSXODWRU -DFRELDQ RU LWV LQYHUVH QRU GR WKH\ UHTXLUH FRPSXWDWLRQ RI WKH IRUZDUG NLQHPDWLFV DW DQ\ WLPH EHIRUH FRQYHUJHQFH LV DFKLHYHG :KHQ WKH LQLWLDO HVWLPDWH RI WKH YDULDEOH LV UHDVRQDEO\ FORVH WR D VROXWLRQ W\SLFDOO\ ZLWKLQ GHJUHHVf FRQYHUJHQFH LVDFKLHYHG ZLWKLQ VL[ ‘ LWHUDWLRQV HYHQ ZLWK DFFXUDFLHV EHWWHU WKDQ ZKLFK PDNHV UHDOWLPH KLJK SUHFLVLRQ LQYHUVH NLQHPDWLFV D UHDOLW\ )LQDOO\ WKH DOJRULWKPV VLPSOLFLW\ LV VXFK WKDW WKH\ FDQ EH SURJUDPPHG DQG H[HFXWHG YHU\ UDSLGO\ HYHQ RQ D SHUVRQDO PLFURFRPSXWHU IRU DQ\ PDQLSXODWRU ZLWK DW PRVW VL[ GHJUHHV RI IUHHGRP 7KLV SURJUDPPLQJ VLPSOLFLW\ PDNHV WKH RQH DQG WZR GLPHQVLRQDO LWHUDWLYH WHFKQLTXHV VXLWDEOH IRU XVH DV RIIn OLQH LQWHUDFWLYH LQYHUVH NLQHPDWLF WRROV DV ZHOO 7KH GLVDGYDQWDJHV RI WKH LQYHUVH NLQHPDWLFV PHWKRGV GHYHORSHG KHUH DUH WKRVH LQKHUHQW WR LWHUDWLYH DOJRULWKPV 1R WKHRUHWLFDO JXDUDQWHH RI FRQYHUJHQFH FDQ EH JLYHQ DQG WKH QXPEHU RI LWHUDWLRQV UHTXLUHG IRU FRQYHUJHQFH GHSHQGV KLJKO\ RQ WKH LQLWLDO HVWLPDWH RI WKH YDULDEOHV $ GLVDGYDQWDJH RYHU WKH KRPRWRS\ PDS PHWKRG 7VDL DQG 0RUJDQ f LV WKDW FRQYHUJHQFH WR RQO\ RQH VROXWLRQ LV SRVVLEOH DJDLQ D FRPPRQ GLVDGYDQWDJH RI LWHUDWLYH WHFKQLTXHV 6HDUFKLQJ IRU PRUH WKDQ RQH VROXWLRQ UHTXLUHV WU\LQJ YDULRXV HVWLPDWHV RI WKH YDULDEOHV 2QH SUREOHP WKDW WKH PHWKRGV GHYHORSHG LQ WKLV WH[W VKDUH ZLWK 7VDL DQG 0RUJDQnV KRPRWRS\ PDS PHWKRG f LV PAGE 140 WKDW WKH DOJRULWKP PD\ FRQYHUJH WR YDOXHV WKDW GR QRW AFRUUHVSRQG WR WUXH LQYHUVH NLQHPDWLF VROXWLRQ VHWV 7KLV UHTXLUHV WKH DGGLWLRQ RI D SRVWFRQYHUJHQFH PHWKRG IRU FKHFNLQJ WKH FRQVLVWHQF\ RI WKH VROXWLRQV WR ILOWHURXW H[WUDQHRXV RQHV $OWKRXJK WKLV SUREOHP KDV QRW EHHQ ERWKHUVRPH LQ SUDFWLFH LW LV RQH WKDW PXVW EH DGGUHVVHG $ WUDGHRII EHWZHHQ UHPRYDO RI H[WUDQHRXV VROXWLRQV DQG FRPSXWDWLRQ FRVW H[LVWV 2QH GHVLUDEOH IXWXUH LPSURYHPHQW RQ WKH RQH DQG WZRGLPHQVLRQDO WHFKQLTXHV ZLOO EH WKH GHYHORSPHQW RI IDVW WHFKQLTXHV IRU WKH HOLPLQDWLRQ RI H[WUDQHRXV VROXWLRQV $QRWKHU IXWXUH UHVHDUFK DUHD LV LQ WKH HVWDEOLVKPHQW RI QHFHVVDU\ VWUXFWXUDO FRQGLWLRQV RI '2) PDQLSXODWRUV IRU WKH DSSOLFDELOLW\ RI WKH RQHGLPHQVLRQDO WHFKQLTXH RU WKH H[LVWHQFH RI FORVHGIRUP VROXWLRQV 7KH VWUXFWXUDO FRQGLWLRQV HVWDEOLVKHG LQ &KDSWHUV DQG DUH VXIILFLHQW EXW QRW QHFHVVDU\ 7KHUH PD\ EH RWKHU VXFK JHRPHWU\ FRQGLWLRQV WR EH GLVFRYHUHG PAGE 141 $33(1',; 62/9,1* )25 ,Q WKH LQYHUVH NLQHPDWLF VROXWLRQ IRU IRXUGHJUHHRI IUHHGRP URERW PDQLSXODWRUV GHVFULEHG LQ &KDSWHU DIWHU VROYLQJ IRU A DQG k ZH VDLG WKDW WKH DQJOH k FDQ EH REWDLQHG E\ VROYLQJ RQH WKH WZR OLQHDU V\VWHPV RI HTXDWLRQV LQ 6 DQG & JLYHQ E\ (TV f DQG f RU (TV f DQG f ,Q WKLV $SSHQGL[ ZH VKRZ WKDW k FDQ DOZD\V EH FRPSXWHG IURP RQH RI WKRVH WZR V\VWHPV ZKHQ WKH '2) DUP LV QRW LQ D GHJHQHUDWH FRQILJXUDWLRQ 7KH DEVROXWH YDOXH RI WKH GHWHUPLQDQW RI WKH V\VWHP RI (TV f DQG f 'A LV JLYHQ E\ A rUFA 7DAA D D&nA $Of DQG LQ DEVROXWH YDOXH WKH GHWHUPLQDQW RI WKH V\VWHP RI (TV f DQG f \LHOGV f§ AU WFA AAfA $f $ YDOXH RI k LV REWDLQHG DV ORQJ DV 'A DQG DUH QRW VLPXOWDQHRXVO\ HTXDO WR ]HUR +RZHYHU ERWK GHWHUPLQDQWV HTXDO ]HUR UHTXLUHV WKDW WKH IRXU FRQGLWLRQV DA f 7DA a $f D D& $f PAGE 142 R $f $f D7 7D& D6 2 EH VLPXOWDQHRXVO\ VDWLVILHG :H QRZ H[DPLQH WKH FRQVHTXHQFHV RI KDYLQJ DOO IRXU FRQGLWLRQV VDWLVILHG &RQGLWLRQ $f UHTXLUHV WKDW D RU 6 &DVH X DQG 6 WKHQ U sO DQG IURP FRQGLWLRQ $f ZH VHH WKDW R PXVW EH HTXDO WR DQG U sOf &RQGLWLRQ $f WKHQ UHTXLUHV WKDW D EXW D D PHDQV WKDW MRLQW D[HV DQG FRLQFLGH DQG WKH DUP LV GHJHQHUDWH &DVH D 6 WKHQ & sO DQG DV LQ WKH SUHYLRXV FDVH X &RQGLWLRQ $f WKHQ EHFRPHV DD LI & O RU DfD LI & O :KHQ & O k f WKHQ DD PHDQV WKDW D D VLQFH ERWK OLQN OHQJWKV D DQG D DUH QRQQHJDWLYH QXPEHUV 7KHUHIRUH WKLV FDVH PHDQV WKDW D D DQG D D VR WKDW MRLQW D[HV DQG FRLQFLGH DQG WKH DUP LV GHJHQHUDWH :KHQ & O k Uf WKHQ DaD DQG D D 6LQFH D D D[HV DQG DUH SDUDOOHO 7KH YDOXHV D D DQFA k U IRUFH MRLQW D[HV DQG WR EH DOLJQHG WKHUHE\ IRUFLQJ WKH DUP LQ D GHJHQHUDWH FRQILJXUDWLRQ &DVH 6 DQG FU IR 7KLV FDVH RFFXUV ZKHQ k RU ZKHQ k 7 :KHQ k WKHQ & O DQG FRQGLWLRQ $f \LHOGV D D DV LQ WKH SUHYLRXV FDVH &RQGLWLRQ $f \LHOGV D RU G 6LQFH D WKH FDVH FU PHDQV WKDW MRLQW D[HV DQG DUH DOLJQHG DQG WKH DUP LV GHJHQHUDWH $VVXPLQJ G DQG PAGE 143 D &RQGLWLRQ $f JLYHV FWW WFW RU VLQDDf 7KH YDOXHV DcD RU LU DQG G D D PHDQ WKDW MRLQW D[HV DQG DUH DOLJQHG VR WKH DUP LV GHJHQHUDWH :KHQ k U WKHQ & O DQG &RQGLWLRQ $f IRUFHV D D ZKLOH &RQGLWLRQ $f QRZ EHFRPHV D77&7 RU VLQDDf 7KH FRPELQDWLRQ RI YDOXHV DDf D D DQG k 7 DJDLQ IRUFH D[LV WR DOLJQ ZLWK D[LV ZKLFK SXWV WKH DUP LQ D GHJHQHUDWH FRQILJXUDWLRQ 6LQFH WKH GHWHUPLQDQWV DQG DUH VLPXOWDQHRXVO\ ]HUR RQO\ ZKHQ WKH PDQLSXODWRU LV GHJHQHUDWH :H FDQ FRQFOXGH WKDW D XQLTXH YDOXH RI k FDQ DOZD\V EH FRPSXWHG DV LQGLFDWHG LQ &KDSWHU ZKHQ WKH DUP LV QRQGHJHQHUDWH PAGE 144 5()(5(1&(6 $QJHOHV 2Q WKH QXPHULFDO VROXWLRQ WR WKH LQYHUVH NLQHPDWLFV SUREOHPn ,QW 5RERWLFV 5HV a f a $QJHOHV ,WHUDWLYH NLQHPDWLF LQYHUVLRQ RI JHQHUDO ILYHD[LV URERW PDQLSXODWRUV ,QW 5RERWLFV 5HV f &UDLJ -,QWURGXFWLRQ WR URERWLFV PHFKDQLFV DQG FRQWURO $GGLVRQ:HVOH\ 5HDGLQJ 0DVVDFKXVHWWV 'HQDYLW DQG +DUWHQEHUJ 56 $ NLQHPDWLF QRWDWLRQ IRU ORZHUSDLU PHFKDQLVPV EDVHG XSRQ PDWULFHV $60( $SSO 0HFK 'RW\ / 0DFKLQH ,QWHOOLJHQFH /DE UHSRUW 0,/ f (OHFWULFDO (QJLQHHULQJ 'HSW 8QLYHUVLW\ RI )ORULGD *DLQHVYLOOH )ORULGD 'RW\ / 7DEXODWLRQ RI WKH V\PEROLF PLGIUDPH -DFRELDQ RI D URERW PDQLSXODWRU ,QW 5RERWLFV 5HV f 'XII\ $QDO\VLV RI PHFKDQLVPV DQG URERW PDQLSXODWRUV -RKQ :LOH\ 1HZ