IntervalMethodsforUncertainPower
SystemAnalysis
AlfredoVaccaro
UniversityofSannio
Italy
Copyright©2023byTheInstituteofElectricalandElectronicsEngineers,Inc. Allrightsreserved.
PublishedbyJohnWiley&Sons,Inc.,Hoboken,NewJersey. PublishedsimultaneouslyinCanada.
Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinany formorbyanymeans,electronic,mechanical,photocopying,recording,scanning,orotherwise, exceptaspermittedunderSection107or108ofthe1976UnitedStatesCopyrightAct,without eitherthepriorwrittenpermissionofthePublisher,orauthorizationthroughpaymentofthe appropriateper-copyfeetotheCopyrightClearanceCenter,Inc.,222RosewoodDrive,Danvers, MA01923,(978)750-8400,fax(978)750-4470,oronthewebatwww.copyright.com.Requeststo thePublisherforpermissionshouldbeaddressedtothePermissionsDepartment,JohnWiley& Sons,Inc.,111RiverStreet,Hoboken,NJ07030,(201)748-6011,fax(201)748-6008,oronlineat http://www.wiley.com/go/permission.
Trademarks:WileyandtheWileylogoaretrademarksorregisteredtrademarksofJohnWiley& Sons,Inc.and/oritsaffiliatesintheUnitedStatesandothercountriesandmaynotbeused withoutwrittenpermission.Allothertrademarksarethepropertyoftheirrespectiveowners. JohnWiley&Sons,Inc.isnotassociatedwithanyproductorvendormentionedinthisbook.
LimitofLiability/DisclaimerofWarranty:Whilethepublisherandauthorhaveusedtheirbest effortsinpreparingthisbook,theymakenorepresentationsorwarrantieswithrespecttothe accuracyorcompletenessofthecontentsofthisbookandspecificallydisclaimanyimplied warrantiesofmerchantabilityorfitnessforaparticularpurpose.Nowarrantymaybecreatedor extendedbysalesrepresentativesorwrittensalesmaterials.Theadviceandstrategiescontained hereinmaynotbesuitableforyoursituation.Youshouldconsultwithaprofessionalwhere appropriate.Neitherthepublishernorauthorshallbeliableforanylossofprofitoranyother commercialdamages,includingbutnotlimitedtospecial,incidental,consequential,orother damages.Further,readersshouldbeawarethatwebsiteslistedinthisworkmayhavechanged ordisappearedbetweenwhenthisworkwaswrittenandwhenitisread.Neitherthepublisher norauthorsshallbeliableforanylossofprofitoranyothercommercialdamages,includingbut notlimitedtospecial,incidental,consequential,orotherdamages.
Forgeneralinformationonourotherproductsandservicesorfortechnicalsupport,please contactourCustomerCareDepartmentwithintheUnitedStatesat(800)762-2974,outsidethe UnitedStatesat(317)572-3993orfax(317)572-4002.
Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappearsin printmaynotbeavailableinelectronicformats.FormoreinformationaboutWileyproducts, visitourwebsiteatwww.wiley.com.
LibraryofCongressCataloging-in-PublicationData:
Names:Vaccaro,Alfredo,author.|JohnWiley&Sons,publisher.
Title:Intervalmethodsforuncertainpowersystemanalysis/Alfredo Vaccaro.
Description:Hoboken,NewJersey:Wiley-IEEEPress,[2023]|Includes index.
Identifiers:LCCN2023014418(print)|LCCN2023014419(ebook)|ISBN 9781119855040(cloth)|ISBN9781119855057(adobepdf)|ISBN 9781119855064(epub)
Subjects:LCSH:Electricpowersystems.|Electricpower systems–Mathematicalmodels.|Electricpowersystems–Reliability.| Systemanalysis.
Classification:LCCTK1005.V252023(print)|LCCTK1005(ebook)|DDC 621.3101/5118–dc23/eng/20230506
LCrecordavailableathttps://lccn.loc.gov/2023014418
LCebookrecordavailableathttps://lccn.loc.gov/2023014419
CoverDesign:Wiley
CoverImage:©Sukpaiboonwat/Shutterstock
Setin9.5/12.5ptSTIXTwoTextbyStraive,Chennai,India
Tomyfamily
Contents
AbouttheAuthor ix
Preface xi
Acknowledgments xiii
Acronyms xv
Introduction 1
1IntroductiontoReliableComputing 3
1.1ElementsofReliableComputing 4
1.2IntervalAnalysis 7
1.3Interval-BasedOperators 8
1.4IntervalExtensionsofElementaryFunctions 9
1.5SolvingSystemsofLinearIntervalEquations 11
1.6FindingZerosofNonlinearEquations 15
1.7SolutionofSystemsofNonlinearIntervalEquations 16
1.8TheOverestimationProblem 20
1.9AffineArithmetic 22
1.9.1ConversionBetweenAAandIA 25
1.9.2AA-BasedOperators 25
1.9.3ChebyshevApproximationofUnivariateNonaffineFunctions 28
1.9.4MultiplicationofAffineForms 31
1.9.5EffectsofRecursiveSolutionSchemes 35
1.10IntegratingAAandIA 35
2UncertainPowerFlowAnalysis 37
2.1SourcesofUncertaintiesinPowerFlowAnalysis 39
2.2SolvingUncertainLinearizedPowerFlowEquations 41
2.3SolvingUncertainPowerFlowEquations 46
2.3.1Optimization-BasedMethod 48
2.3.2DomainContractionMethod 52
3UncertainOptimalPowerFlowAnalysis 59
3.1RangeAnalysis-BasedSolution 61
3.1.1OptimalEconomicDispatch 63
3.1.2ReactivePowerDispatch 66
3.2AA-BasedSolution 70
4UncertainMarkovChainAnalysis 75
4.1MathematicalPreliminaries 77
4.2EffectsofDataUncertainties 78
4.3MatrixNotation 79
4.4AA-BasedUncertainAnalysis 80
4.5ApplicationExamples 83
4.5.1CaseStudy1:GridResilienceAnalysis 83
4.5.2CaseStudy2:EnergyStorageModel 84
4.5.3Summary 86
5Small-SignalStabilityAnalysisofUncertainPower Systems 87
5.1ProblemFormulation 89
5.2TheIntervalEigenvalueProblem 90
5.3Applications 92
5.3.1CaseStudy1 92
5.3.2CaseStudy2 93
6UncertainPowerComponentsThermalAnalysis 95
6.1ThermalRatingAssessmentofOverheadLines 96
6.1.1SourcesofDataUncertainties 98
6.1.2AA-BasedThermalRatingAssessment 99
6.1.3ApplicationExamples 100
6.2ThermalRatingAssessmentofPowerCables 104
6.2.1ThermalModelingofPowerCables 105
6.2.2SourcesofDataUncertainties 107
6.2.3ToleranceAnalysisofCableThermalDynamicsbyIA 108
6.2.4ApplicationExamples 109
References 112 Index 119
AbouttheAuthor
AlfredoVaccaro,PhD,isafullprofessorofelectricpowersystemsatthe DepartmentofEngineeringofUniversityofSannio.Heistheeditor-in-chiefof SmartGridsandSustainableEnergy,SpringerNatureandassociateeditor ofIEEEtrans.onSmartGrids,IEEEtrans.onPowerSystems,andIEEEPower EngineeringLetters.
Preface
Thisbooksummarizesthemainresultsofmyresearchactivitiesinthefieldof uncertainpowersystemanalysisbyintervalmethods.
Istartedworkingonthisinterestingandchallengingissueinearly2000, inspiredbythepapersofProf.FernandoAlvaradoabouttheapplicationof intervalarithmeticinuncertainpowerflowanalysis.Thefirstcontributionswere focusedonmitigatingtheeffectsofthe“dependencyproblem”and“wrapping effect”inintervalanalysis,whichcanreducethevalueoftheresultsbyoverestimatingtheboundsofthepowerflowsolutions.Thisoverestimationproblem hasbeenobservedwhensolvingmanyconventionalpowersystemoperation problemsby“naive”intervalanalysis,whichmayleadtoaberrantsolutions, duetotheinabilityofintervalarithmetictomodelthecorrelationsbetweenthe uncertainvariables.Consequently,eachstepofthealgorithmintroducesspurious values,causingthesolutionboundstoconvergetooverconservativevalues. Thisphenomenahasbeenextensivelystudiedinqualitativesystemsanalysisand requirestheuseofcomplexandtime-consumingpreconditioningtechniques.
ThisstimulatedtheresearchintoalternativeintervalmethodsbasedonAffine Arithmetic,whichisoneofthemaintopicsofthisbook.
Inthisapproach,eachuncertainvariableisdescribedbyafirst-degreepolynomialcomposedofacentralvalueandanumberofpartialdeviations,eachone modelingtheeffectofanindependentsourceofuncertainty.
TheadoptionofAffineArithmeticmakesitpossibletosolveuncertain mathematicalprogrammingproblemsandobtainareliableestimationofthe solutionhullsbyincludingtheeffectofcorrelationbetweentheuncertain variables,aswellastheheterogeneityofthesourcesofuncertainty.
Thisreliablecomputingparadigmhasbeensuccessfullydeployedtosolvealarge numberofpowersystemoperationproblemsinthepresenceofdatauncertainty. Theexamplespresentedinthisbookcoverpowerflowstudies,optimalpower flowanalysis,dynamicthermalratingassessment,stateestimation,andstability analysis.
xii Preface
Theobtainedresultsdemonstratetheeffectivenessofintervalmethodsto solvethecomplexuncertainproblemsencounteredwhenanalyzingrealistic powersystemoperationscenarios,hence,makingthesemethodsoneofthe mostpromisingalternativesforstochasticinformationmanagementinmodern powersystems.
May2023
AlfredoVaccaro Benevento,Italy
Acknowledgments
IwishtoexpressmysinceregratitudetomymentorProf.ClaudioCanizares,who inspiredandstimulatedmyresearchactivitiesinthefieldofuncertainpower systemanalysis.
IwouldalsoliketothankProf.KankarBhattacharyaforhisvaluableand qualifiedsuggestionsaboutthepotentialroleofrangeanalysisinmarketstudies, andDr.AdamJ.CollinandDr.FabrizioDeCarofortheirvaluablesupportin reviewingthisbook.
AlfredoVaccaro
Acronyms
AAaffinearithmetic
DTRdynamicthermalrating
IAintervalanalysis
IMintervalmathematics
MCMarkovChain
OPFoptimalpowerflow
PFpowerflow
Introduction
Powersystemanalysisisoftenaffectedbylargeandcorrelateduncertainties, whichcouldseriouslyaffectthevalidityoftheobtainedresults.Uncertaintiesin modernpowersystemsstemfrombothinternalandexternalfactors,including modelinaccuracies,measurementerrors,inconsistentdata,andimprecise knowledgeaboutsomeinputinformation.
Conventionalmethodsforuncertaintymodelinginpowersystemanalysis involveusingprobabilistictechniquestocharacterizethevariabilityininput dataandsampling-basedapproachestosimulatethesystembehaviorforalarge numberofpossibleoperatingscenarios.
However,relyingonprobabilisticmethodshasitslimitations,aspowersystem engineersmaystruggletoexpresstheirimpreciseknowledgeaboutcertaininput variableswithprobabilitydistributions(duetothesubjectiveandqualitative natureoftheirexpertise),and,moregenerally,theremaybealackofreliabledata forcharacterizingtheprobabilityparameters.Additionally,theuseofprobabilistic methodsoftenrequirestheassumptionsofnormaldistributionsandstatistical independence,e.g.inthecaseofweathervariables,butoperationalexperience showsthattheseassumptionsarefrequentlyunsupportedbyempiricalevidence.
Recentadvancesinthefieldhaveexpandedtherangeofmethodsforaddressinguncertaintybyintroducinganumberofnonprobabilistictechniques,suchas intervalanalysis,fuzzyarithmetic,andevidencetheory.
Nonprobabilistictechniquesareoftenusedwhenuncertaintyarisesfrom limitationsinourunderstandingofthesystem,ratherthanunpredictablenumericaldata.Inthesecases,onlyroughestimatesofvaluesandrelationshipsbetween variablesareavailable.Consider,forexamplethepowerprofilesgeneratedby smallanddispersedrenewablegenerators,whichstrictlydependontheevolution ofsomeweathervariables,e.g.solarradiationforphotovoltaicgeneratorsand windspeedanddirectionforwindturbines.Althoughthesevariablescanbe measuredataspecificlocation,itischallengingtodeterminetheirdistributions overawidegeographicalarea.Nonetheless,weatherforecastsperiodicallyprovide IntervalMethodsforUncertainPowerSystemAnalysis,FirstEdition.AlfredoVaccaro. ©2023TheInstituteofElectricalandElectronicsEngineers,Inc.Published2023byJohnWiley&Sons,Inc.
qualitativeinformationabouttheexpectedevolutionoftheweathervariableson differenttimehorizons,butthesepredictedprofilescannotbeeasilyexpressedas probabilities.
Itfollowsthattheavailabilityofreliableframeworksformodelingandmanaging nonprobabilisticknowledgecangreatlyenhancetherobustnessandeffectiveness ofpowersystemanalysis.
Forthispurpose,intervalmethodshavebeenrecognizedasanenablingmethodologyforuncertainpowersystemanalysis.
Theprimarybenefitofthesetechniquesisthattheyintrinsicallykeeptrack ofthecomputingaccuracyofeachelementarymathematicaloperation,without needinginformationorassumptionsabouttheinputparameteruncertainties.
Thesimplestandmostcommonlyusedofthesemodelsisintervalmathematics, whichenablesnumericalcomputationsinwhicheachvalueisrepresentedbya rangeoffloating-pointnumberswithoutaprobabilitystructure.Theseintervals areprocessedbyproperaddition,subtraction,and/ormultiplicationoperators, ensuringthateachcomputedintervalenclosestheunknownvalueitrepresents.
Manyanalystsviewintervalmathematicsasasubsetoffuzzytheory,asinterval variablescanbeviewedasaspecificinstanceoffuzzynumbers.However, connectingintervalmathematicstofuzzysettheoryisnotstraightforward. Recently,fuzzysettheoryandintervalanalysishavebothbeenlinkedtoabroader topologicaltheory.Similarly,itisarguedthatfuzzyinformationgranulation, roughsettheory,andintervalanalysisareallsubsetsofalargercomputationalparadigmcalledgranularcomputing,wherethesemethodologiesare complementaryandsymbiotic,ratherthanconflictingandexclusive.
Thisbookfocusesontheapplicationofintervalmethodsinuncertainpower systemanalysis.Inparticular,afterintroducingthebasicelementsofinterval computing,asetofconventionalpowersystemoperationproblemsinthe presenceofdatauncertaintiesareformalizedandsolved.Manynumerical examplesarepresentedanddiscussedinordertodemonstratetheeffectiveness ofintervalmethodstoreliablysolvethecomplexproblemsencounteredwhen analyzingtherealisticoperatingscenariosofmodernpowersystems.
1.1ElementsofReliableComputing
Let f ∶ Rm → Rn beacontinuousmathematicalfunction,andsupposeweneedto compute z = f (x ) for x ∈ Rm .Forthis,weshouldimplementadiscretenumerical computation Z = F (X ),where X and Z arediscretemathematicalobjectsapproximatingthecorrespondingcontinuousvariables x and z. Tosolvethisissuedifferentreliablecomputingmodelscanbeadopted,including probabilitydistributionsandrange-basedmethods.
Inparticular,theadoptionofprobabilitydistributionscanapproximate,ina statisticalsense,thecomputedresult Z byconsideringeachcomponentofthe vector z asareal-valuerandomvariable,whoseprobabilitydistributionfunction isfrequentlyassumedtofollowaGaussiandistribution.Inthiscase,areliable computingmodelshouldspecifythestatisticalmomentsofeachcomponent zi , andthecorrespondingcovariancematrixdescribingthejointGaussianprobabilitydistributionoftherandomvector (z1 , , zn ),giventhosecharacterizingthe randominputvariables (x1 , , xm )
Theapplicationofthisprobabilistic-basedreliablecomputingmodelisoften limitedtospecificapplicationdomains,whicharecharacterizedbyGaussian uncertainties,linearmappings,andnegligibletruncationerrors.Thelackofthese conditionsmakesthestatisticalcharacterizationofthecomputedresultextremely complexorevenmathematicallyintractable(StolfiandDeFigueiredo,1997).
Totryandovercomethislimitation,mostreliablecomputingmodelsapproximatethecomputedresultsbyranges,ratherthanbyprobabilitydistributions.
Accordingtothesemodels,theapproximatedsolution Z isdescribedbymeans ofitsrange [Z ],whichisacompactsetcontainingthe“exact”solutions z = f (x ) foralltheinputvariables x lyingintherange [X ].
Thisimportantfeature,whichisusuallyreferredtoasthe fundamentalinvariant ofrangeanalysis,guaranteesthattherange [Z ] containsthetruesolutionset, providedthattheinputvariablesvaryinafixedrange.
ThesimplestmodelofrangeanalysisisIntervalArithmetic(Moore,1966), whichdefinestherangeofeachcomponentofthecomputedresult [Zi ] bya realinterval,whichisasetofrealnumberslyingbetweenitsupperandlower bounds.Sincenoconstraintsrelatingtheseintervalsareassumed,meaningthat alltheuncertaintiesareassumedtobestatisticallyindependent,therangeofthe computedresult [Z ] istheCartesianproductoftherangesofitscomponents [Zi ], sinceallcombinationsof z1 , … , zn inthebox [Z1 ]×···×[Zn ] areallowed.
Inmoreadvancedreliablecomputing-basedmodels,suchasthosebasedon affinearithmetic(AA),thecomputedresultalsointegratesusefulinformation aboutthepartialcorrelationsbetweentheoutputvectorcomponents zi ;hence, identifyingthestatisticaldependenciesbetweentheinputvariables xi andthe computedresult.Inthiscase,therangeofthecomputedresult [Z ] isaproper subsetoftheCartesianproductoftheindividualranges.
Oneofthemostimportantfeatureswhichcharacterizesallrange-basedmodels istheircapabilityofcomputing,foreveryfunction f ∶ Rm → Rn ,a rangeextension F ∶ ℜm → ℜn ,whichischaracterizedbythe fundamentalinvariantofrange analysis:
Iftheinputvector x =(x1 , … , xm ) liesintherangejointlydeterminedbythe givenapproximatevalues X =(X1 , … , Xm ),thenthequantities z =(z1 , … , zn )= f (x1 , … , xm ) areguaranteedtolieintherangejointlydefinedbytheapproximate values Z =(Z1 , , Zn )= F (X1 , , Xm ).
Thispropertyisextremelyusefulinreliablecomputing,sincethejointrange determinedbytheapproximatedvalues Zi isanouterestimationoftherealsolutionset,namely: S ={z ∶ z = f (x1 , … , xm ), x1 ∈ X1 , … ., xm ∈ Xm } ⊆ Z (1.1)
hence,introducingaconservativefactorinapproximatingthesolutionvectors. Thisconservativismisavaluablefeatureofrangeanalysis-basedmethods,which isextremelyimportantinreliablepowersystemanalysis,sinceitallowsthe Analysttoboundallinternalandexternaluncertaintiesinnumericalcomputing. However,obtainingasuitable(nottoolarge)conservativismlevelisarelevant probleminrange-basedcomputation,sincethenaiveapplicationofrange-based modelsoftenresultsinextremelyconservativesolutionranges,whicharetoo wide,andhence,notusefulinrealisticapplicationdomains.
Therefore,inordertoassessandcomparetheconservativismofrange-based reliablecomputingmodels,propermetricsshouldbedefined.Forthispurpose, weintroducethe relativeaccuracy oftherange-basedapproximation Z ,whichis definedas:
where ||Y
and
[Z ]|| arethenormsoftherealsolutionrange Y
(
)∶ x ∈[X ]} andthecomputedrange [Z ],respectively.
Thisindexisareliablemeasureoftheconservativismintroducedbyrange-based computing,indicatingtheouterestimationaccuracybyanumber,whichcould varybetweenzero(i.e.thecomputedrangeismuchwiderthantherealone)and one(i.e.noconservativismisintroducedinrangecomputing).
Obviously,thisindexrequiresthattheinputvector x =(x1 , … , xm ) shouldvary intherangejointlydeterminedbythegivenapproximatevalues X =(X1 , , Xm ), asstatedbythefundamentalinvariantofrangeanalysis.Thishypothesiscannot beverifiedinrealapplicationdomains,wheresomeoftheinputdataareacquired bymeasurements,whichcanbeaffectedbyunboundederrors.Inthiscontext, theassumptionrelatedtotheinclusionoftheoutputvariables z intherange jointlydeterminedbytheapproximatevalues Z shouldberevisedbyintroducing probabilisticinformationabouttherangeofthepossiblevalues [Z ].Thisrequires determining,forthecomputedrange[Z],thecorresponding confidencerangepZ , whichistheprobabilityof z tobeincludedin[Z].Thisapproachdiffersfrom theGaussian-basedprobabilisticmodelsasitdoesnotassumeanyhypothesis abouttheprobabilitydistributionoftheerrorinsidetherange [Z ],butonlythat itsintegraloverthecomputedrangeisatleast pZ .
Hence,theapplicationofrange-basedmethodsinthiscontextrequirescomputing,foreachmathematicaloperation,notonlythejointrange,butalsoaconservativeestimationofthecorrespondingconfidencelevel,asafunctionofthe confidenceleveloftheinputdata.
1.2IntervalAnalysis
Intervalanalysis(IA),alsoreferredtoasintervalarithmetic,isarange-based modelfornumericalcomputingthatdescribeseachuncertainvariable x byan intervalofrealnumbers x ,whichisguaranteedtocontainthe(unknown)“true” valueof x (Moore,1966).
Morespecifically,arealintervalisacompactset,whichisdefinedas:
where xlo and xhi arethelowerandupperboundsoftheinterval,respectively.
Thoseintervalsarecombinedandprocessedbyspecificmathematicaloperators,whichgeneralizeallthereal-valuefunctionstoprocessinterval-based uncertainvariables,insuchawaythatthecomputedintervalsareguaranteed tocontainallthepossiblevaluesofthecomputedquantities.Toachievethis, IAdefinesforeachmathematicalfunction z = f (x1 , , xn ) with xi ∈ R aproper intervalextension z = f (x 1 , , x n ),whichallowscomputationofaninterval z that containsallthevalues z = f (x ) for (x1 , … , xn ) varyingindependentlyoverthe givenintervals (x 1 , … , x n ).
Computingintervalextensionforlinearfunctionsisextremelysimple,sinceit onlyrequiresdefiningaclosedformexpressionfortheextremevaluesofthefunctionwhenitsargumentsvaryindependentlyoverspecifiedintervals.
Onthecontrary,computingintervalextensionsfornonlinearfunctionsisa verycomplexissue.Indeed,defininganalyticformulaforcomputingthe“exact” extremevaluesofthesefunctionscanbeextremelydifficult.Hence,inorderto satisfythefundamentalinvariantofrangeanalysis,aconservative(buteasily computable)approximationofthe“exact”functionrangeshouldbeidentified. Inthesecases,thecorrespondingcomputedintervalsareouterestimationsofthe “exact”solutionsets.
Theintervalextensionsofthemainmathematicaloperatorsandelementary functionscanbecomposedinordertocomputetheintervalextensionsforany complexfunctionbyusingthesamemathematicalschemesadoptedinreal numberscomputing.Hence,anynumericalalgorithmprocessingrealnumbers canbeautomaticallydeployedforprocessingintervalvariablesbyreplacingthe realnumberoperatorsandfunctionswiththeircorrespondingintervalextensions. Thisschemeallowsthenumericalalgorithmstoevolvefromcomputingwith realnumberstocomputingwithintervalsandtoidentifysolutionswhichare nolongerdeterministic(validonlyforfixedrealinputdata),butdescribedby intervalsthat,accordingtothefundamentalinvariantofrangeanalysis,are
1IntroductiontoReliableComputing
guaranteedtoincludetherealvaluesofthesolutionsforallinstancesofthe uncertaininputdata(thatshouldvaryinthespecifiedintervals).
1.3Interval-BasedOperators
Theintervalextensionsofthebasicmathematicaloperatorscanbeeasilydefined asfollows:
x =[−xhi , xlo ]
x + y =[xlo + ylo , xhi + yhi ]
x + c =[xlo + c, xhi + c]
x y =[xlo yhi , xhi ylo ]
c x =[c xlo , c xhi ]c > 0
c ⋅ x =[c ⋅ xhi , c ⋅ xlo ]c < 0
(1.4)
Todefinetheintervalextensionofthemultiplication, x ∗ y,itisnecessaryto deriveananalyticexpressionoftheminimumandmaximumvaluesofthefunction xy for (x , y) varyingovertherange [xlo , xhi ]×[ylo , yhi ].Tosolvethisproblem,it shouldbenotedthatthefunction xy islinearin y (x )foreachfixed x (y);hence,its maximumandminimumvalues,referredtoas a and b,respectively,arelocatedat thecorneroftherectangle [xlo , xhi ]×[ylo , yhi ],namely:
a = min {xlo ⋅ ylo , xlo ⋅ yhi , xhi ⋅ ylo , xhi ⋅ yhi }
b = max {xlo ylo , xlo yhi , xhi ylo , xhi yhi }
(1.5)
Thesameschemecanalsobeadoptedforcomputingtheintervalextensionof thedivision, x ∕y,whichcanberepresentedastheproductof x by1∕y.Inthiscase,it shouldbenotedthatthereciprocalfunction1∕y isnotdefinedfor y = 0;hence, thisconditionshouldbeproperlycheckedasfollows:
if ylo < 0and yhi > 0then a =−∞, b =+∞
if yhi = 0then a =−∞
if yhi ≠ 0then a = 1 yhi
if ylo = 0then b =+∞
if ylo ≠ 0then b = 1 ylo
(1.6)
Theseinterval-basedarithmeticoperatorsgeneralizethearithmeticofrealnumberstothesetofrealintervals.
Otherusefulintervaloperatorsincludethemidpoint m(x ) andtheradius r (x ) of theinterval x ,whicharedefinedas:
m(x )= xlo + xhi 2
r (x )= xhi xlo 2
Moreover,itisalsousefultodefinetheintersectionoftwointervals x and y, whichisdefinedas:
x ∩ y =[max {xlo , ylo }, min {xhi , yhi }]
andtheconvexhulloftwointervals x and y,whichisthesmallestinterval x ∪ y containing [min {xlo , ylo }, max {xhi , yhi }]
Finally,inordertosolvemultidimensionalproblems,wedefineinterval matrices A =(aij ) with i ∈[1, m] and j ∈[1, n],andintervalvectors x =(x i ),with i ∈[1, n],whicharedefinedasfollows(GötzandGünter,2000):
[Alo , Ahi ]={B ∈ Rmxn ∶ Alo ≤ B ≤ Ahi }
Therealmatrix A ∈(Rnxn ) issaidtobean M matrix,if aij ≤ 0for i ≠ j andif A 1 existsandisnonnegative.Thisdefinitioncanbegeneralizedtointervalmatrices; inparticular,ifeachmatrix A fromagivenintervalmatrix A isan M matrix,then theintervalmatrix A isan M matrix.
Startingfromthesedefinitions,itispossibletoexpresstheproduct Ax asfollows:
Hence, Ax istheintervalvectorcontainingtheleftsetin(1.9).
Anintervalvectorenclosingsomeset S astightaspossibleiscalledthe(interval) hullof S.
1.4IntervalExtensionsofElementaryFunctions
Computingtheintervalextensionofthesquarerootisstraightforwardsincethis functionismonotonic,andapreliminarycheckoftheinputrangeisonlyrequired, asfollows: if xlo < 0and xhi < 0then √x =[] if xlo < 0and xhi > 0then √x =[0, √xhi ] if xlo > 0and xhi > 0then √x =[√xlo , √xhi ] (1.10)
1IntroductiontoReliableComputing
Asimilarapproachcanbeadoptedfordefiningtheintervalextensionofthe logarithmlog(x ) (whichisnotdefinedatzero)andtheexponentialexp(x )= ex , whicharedescribedin(1.11)and(1.12),respectively.
if xhi < 0thenlog x =[]
if xlo < 0and xhi > 0thenlog x =[−∞, log xhi ]
if xlo > 0and xhi > 0thenlog x =[log xlo , log xhi ]
ex =[exlo , exhi ]
Thedefinitionofintervalextensionoftrigonometricfunctionsisnottrivial, becausetheycouldbenonmonotonicintheconsideredinputinterval,butthis canbeobtainedbycomputingthemaximumandminimumfunctionvaluesfor inputsvaryinginthespecifiedinterval,whichforcosandsinfunctionsoccurat integermultiplesof �� and �� ∕2,respectively.Hence,thefollowingprocedurescan beadoptedforcomputingthecorrespondingintervalextensionofcosandsin functions,respectively:
if k�� ∈ x (k = 0, 2, 4, …) then b = 1
else b = max (cos(xlo ), cos(xhi ))
if k�� ∈ x (k = 1, 3, 5, …) then a =−1
else a = min (cos(xlo ), cos(xhi ))
cos x =[a, b] (1.13)
if k �� 2 ∈ x (k = 0, 2, 4, …) then b = 1
else b = max (sin(xlo ), sin(xhi ))
if k �� 2 ∈ x (k = 1, 3, 5, …) then a =−1
else a = min (sin(xlo ), sin(xhi ))
sin x =[a, b] (1.14)
Thesecomputingprocedurescanbeproperlygeneralizedinordertocompute theintervalextensionofanyelementaryfunction f ∶ D ⊆ Rn → Rm with x ⊆ D, which,thankstothefundamentalinvariantofrangeanalysis,isanenclosureof thecorrespondingfunctionrange.
TheeffectivenessofIAinconservativelyestimatingtherangeofanyelementary functionwhentheinputsrangesoverassignedintervalsisaneffectivetool,which canbeusedforeffectivelysolvingcomplexmathematicalproblems,suchas:
1.Computingtheglobalminimaofscalarfunctions
2.EstimatingtherangeoftheJacobianmatrix
3.Verifyingandenclosingsolutionsofinitialvalueproblems, 4.Computingthezerosofscalarfunctions.
1.5SolvingSystemsofLinearIntervalEquations
IA-basedcomputingcanbeappliedtosolvethefollowinguncertainlinear problem:
Ax = b (1.15)
where A and b areknown n × n intervalmatrix,and n-dimensionintervalvector, respectively.Theseknownquantitiescanbeexpressedas:
A =[m(A)− r (A), m(A)+ r (A)]
b =[m(b)− r (b), m(b)+ r (b)] (1.16)
where m(A) (m(b))and r (A) (r (b))arethecenterandtheradiusoftheinterval matrix A (intervalvector b),respectively.
Thesolutionsetoftheselinearequationsisdefinedas:
X ={x ∈ Rn ∶ Ax = b, A ∈ A, b ∈ A} (1.17)
Ourtaskistoidentifyanouterintervalenclosureofthisset. Tothisaim,let’sdefinethefollowing:
1. e =(1, 1, … , l)T ∈ Rn
2. f =−e,
3. Y ={y ∶ |y| = e, y ∈ Rn },sothat Y has2n elements.Forexample,for n = 2 Y ={(1, 1);(−1, 1);(1, 1);(−1, 1)}
4. ∀z ∈ Rn , Tz isthediagonalmatrixwiththevectorcomponents zi onitsdiagonal (namely diag(Tz )={z1 , , zn })
5. Ayz = m(A)− Ty r (A)Tz and by = m(b)+ Ty r (b)∀y, z ∈ Rn
6. dy = m(A) 1 by
7. by = m(b)+ Ty r (b)
Thankstothesedefinitions,itispossibletorigorouslysolvetheproblem(1.15) bysolvingthefollowing2n linearcomplementaryproblems:
x + = A 1 ye Ayf x + A 1 ye by ∀y ∈ Y (1.18) (2.4).
Thesolutionofthisproblemforeach y ∈ Y ,herereferredtoas xy ,maybe obtainedusingconventionaltechniquesforsolvinglinearcomplementarity
1IntroductiontoReliableComputing
problems.Oncethese2n solutionshavebeencomputed,theouterinterval estimationofthesolutionsetcanbeeasilyobtainedasfollows:
xlo = min (xy ∶ y ∈ Y )
xhi = max (xy ∶ y ∈ Y ) (1.19)
However,inordertosimplifythesolutionprocess,i.e.byavoidingtheinversion ofthematrix Aye ,itispossibletorecasttheproblem(1.18)asfollows:
Ayz x = by Tz x ≥ 0
z ∈ Y (1.20)
Thisproblemcanbesolvedbysolvingthesystems Ayz x = by ,fordifferent z’s untilsatisfyingthecondition Tz x ≥ 0,whichisequivalentto zj xj ≥ 0foreach j Hence,thefollowingalgorithmcanbeadoptedtosolvetheproblem(Rohn,1989):
Algorithm
● Step0:Select z ∈ Y (recommended z = sign(dy ))
● Step1:Solve Ayz x = by
● Step2:If Tz x ≥ 0set xY = x andterminate
● Step3:Otherwise,find k = min (j; zj xj < 0) (1.21)
● Step4:Set zk =−zk andgotoStep1.
if A isregular,namelyifeach A ∈ A isnonsingular,thenthisiterativescheme convergesinafinitenumberofstepsforeach y ∈ Y andforanarbitrarystarting z ∈ Y instep0(Rohn,1989).
Inmanyrealisticcases,computing xy onlyrequiresthesolutionofasingle system Ayz x = by ,andthereisnoneedtocomputeall2n vectors yz;hence,a subsetof Y canbeconsideredingeneratingthevectors y
Example1.1 Let’sconsiderthefollowingsetoflinearintervalequations:
Inthiscase,itfollowsthat:
